Loading required package: plotly
Loading required package: ggplot2
Registered S3 method overwritten by 'dplyr':
method from
print.rowwise_df
Registered S3 method overwritten by 'data.table':
method from
print.data.table
Registered S3 methods overwritten by 'htmltools':
method from
print.html tools:rstudio
print.shiny.tag tools:rstudio
print.shiny.tag.list tools:rstudio
Registered S3 method overwritten by 'htmlwidgets':
method from
print.htmlwidget tools:rstudio
Attaching package: ‘plotly’
The following object is masked from ‘package:ggplot2’:
last_plot
The following object is masked from ‘package:stats’:
filter
The following object is masked from ‘package:graphics’:
layout
Loading required package: scales
A Bayesian is one who, vaguely expecting a horse, and catching a glimpse of a donkey, strongly believes he has seen a mule
Why might someone use Bayesian rather than traditional frequentist?
- If they have prior beliefs as to the truth before an experiment is conducted
- If you want to predict how the distribution of a population might change, rather than a point estimate. For example, traditionally, we might try and predict the mean number of people who choose to order after going on our website.
Quick recap of the ‘Classical Approach’ (‘Frequentist’)
set.seed(0)
p <- 0.5
n <- 10
Let’s say we have a coin, and we want to know the probability that we flip heads. Frequentists assume that there is only one true, fixed, unknown probability that the coin yields heads. For ease of notation, let’s call the constant parameter \(p(\text{head}) = \theta\).
To try and discover the true probability of getting a head, we flip the coin 10 times, and count the number of heads to estimate the probability. Frequentists believe that if we repeated this sampling proceedure of 10 flips many, many times, we should expect the average across all of our samples to be reflective of the true population value (hence why it is called ‘frequentist’).
# Create repeated samples
num_repeated_samples <- 10^3
repeated_samples <- rbinom(n = num_repeated_samples, size = n, prob = p)
repeated_samples.cum_p_mean <- cumsum(repeated_samples)/cumsum(rep(n, num_repeated_samples))
# Cumulative mean tends to p
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = 1:length(repeated_samples), y = repeated_samples.cum_p_mean, name = 'Cumulative mean with sampling') %>%
layout(showlegend = F
, yaxis = list(range = c(0, 1))
, title = "Cumulative sample means tends to true p") # ,
k <- round(n*p*0.5,0) # make up fake k that is 'unlikely'
sample_mean <- k/n
binomial_probability <- function(k, n, p) {
n_choose_k <- factorial(n)/(factorial(k)*factorial(n-k))
# NOTE - equivalent to gamma_function(k+n-k)/(gamma_function(k)*gamma_function(n-k), or 1/B(k,n-k)
prob_sample <- n_choose_k*(p)^k*(1-p)^(n-k)
return(prob_sample)
}
k_heads_maxprob <- round(binomial_probability(k,n,k/n),4)*100
k_heads_actprob <- round(binomial_probability(k,n,p),4)*100
np_heads_actprob <- round(binomial_probability(n*p,n,p),4)*100
But in the real world, it’s not possible to take lots of samples over and over again - and we generally just take one. Taking a sample one time, we might observe 2 heads. This is equivalent to creating a sample of size \(10\) and observing a mean probability of \(0.2\).
We don’t know what the true probability of flipping heads is (\(\theta\)), but we can plot the likelihood of observing 2 heads for every possible \(\theta\) the coin might be. On the left graph below, for every possible value that the probability of flipping heads could be on the x axis (somewhere between 0 and 1), the likelihood of observing \(2\) heads is plotted on the y axis, giving the orange line. For example, the likelihood of observing \(2\) heads if the probablity of flipping heads is \(0.2\) is \(30.2\%`\). If the probablity of flipping heads is actually \(0.125\), then the likelihood of flipping 2 heads in our sample is only \(4.39\%\).
It appears most probable from our sample then that our true probability is indeed 0.2 - the most likely probability is what we observe as the mean in our sample (the maximum likelihood estimation is rsample_mean). Thus, a frequentist would conclude that the most likely value of \(\theta\) is \(0.2\), and that the true value of \(\theta\) is hopefully near to it.
However, despite treating the true \(\theta\) as a fixed (non-random) value, frequentists acknowledge there is random sampling error. Even if the probability of flipping heads remaining constant, sometimes there will be 2 heads, sometimes there will be 10 heads etc simply due to chance. We can illustrate this by plotting the likelihood of observing different numbers of heads given a fixed value of \(\theta\). In the graph on the right, the probability of getting different numbers of heads between 0 and 10 is plotted in green if the value of theta is \(0.2\), and blue if the probability is \(0.125\).
In this way then, despite believing the actual (population) probability \(\theta\) to be fixed at one value (and from the sample, the most probable being \(0.2\)), the graph on the right illustrates how frequentists believe that the number of heads observed is a random variable (conditioned by \(\theta\)). By random variable, this means that the number of heads could be many different values before sampling (0-10) rather than being pre-determined/fixed as how they treat \(\theta\). The likelihood of observing any of these possible values is conditioned by the fixed probability \(\theta\) as per the distribution on the right (if the true value of \(\theta\) is \(0.125\), then observing \(1.25\) heads in our sample is a lot more likely than observing \(10\), and observing \(2\) heads is very unlikely).
# for all the different values of theta, p(H=2|θ)
theta_prob_k_heads <- sapply(seq(0,1,0.01), FUN = function(p) binomial_probability(k=k,n=n,p=p))
# for all the different values of outcome k, p(H=k|θ=0.2)
likelihood_est <- sapply(seq(0,10,1), FUN = function(s) {binomial_probability(k=s,n=n,p=k/n)})
# for all the different values of outcome k, p(H=k|θ=0.5)
likelihood_act <- sapply(seq(0,10,1), FUN = function(s) {binomial_probability(k=s,n=n,p=p)})
subplot(
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = seq(0,1,0.01), y = theta_prob_k_heads, name = paste0('P(H=',k,'|θ)')) %>%
layout(xaxis = list(title = 'θ'))
, plot_ly(type = 'scatter', mode = 'lines+markers') %>%
add_trace(x = seq(0,10,1), y = likelihood_est, name = paste0('p(H=k|θ=',k/n,')')) %>%
add_trace(x = seq(0,10,1), y = likelihood_act, name = paste0('p(H=k|θ=',p,')')) %>%
layout(xaxis = list(title = '# heads'))
, shareY = T
, nrows = 1)
#
# plot_ly(type = 'scatter', mode = 'lines') %>%
# add_trace(x = x, y = likelihood_est, name = 'Estimated from sample') %>%
# add_trace(x = x, y = likelihood_act, name = 'Actual likelihood') %>%
# layout(title = "Likelihood function: X ~ Binom(n,p)"
# , xaxis = list(title = 'theta')
# , yaxis = list(title = 'likelihood'))
Hence, to acknowledge that there is randomness associated with this sample mean, frequentists construct confidence intervals. Again to follow the frequentist interpretation, a 95% confidence interval means that, if the sampling proceedure was repeated many, many times, that 95% of the time the true value of \(\theta\) would fall within the confidence interval. (Nuanced note - this is not the same as saying that, in one sample, there is a 95% chance that the true value of \(\theta\) lies within it. This is because \(\theta\) is a fixed value, not a random variable, so it either falls within the sample confidence interval or not.)
true.p.se <- sqrt(p*(1-p)/n)
## BINOMIAL (NORMAL APPROXIMATION)
# The larger the number of successes, np, and failures, n(1-p), the better the normal approximation for confidence intervals (p near 0.5, n as large as possible)
sample.binom.k <- rbinom(n = num_repeated_samples, size = n, prob = p)
sample.binom.p <- sample.binom.k/n
## population standard error/confidence interval
true.binom.p.conf.02.5 <- sample.binom.p-1.96*true.p.se
true.binom.p.conf.97.5 <- sample.binom.p+1.96*true.p.se
true.binom.theta_in_conf <- true.binom.p.conf.02.5 < p & true.binom.p.conf.97.5 > p
## sample standard error/confidence interval
sample.binom.p.se <- sqrt(sample.binom.p*(1-sample.binom.p)/n)
sample.binom.p.conf.02.5 <- sample.binom.p-1.96*sample.binom.p.se
sample.binom.p.conf.97.5 <- sample.binom.p+1.96*sample.binom.p.se
sample.binom.theta_in_conf <- sample.binom.p.conf.02.5 < p & sample.binom.p.conf.97.5 > p
## BETA DISTRIBUTION (CONTINUOUS VERSION OF BINOMIAL)
# Since the binomial distribution is non-continuous, we can get confidence intervals closer to 95% from the equivalent beta distribution for the same np & n(1-p)
sample.beta.k <- rbeta(n = num_repeated_samples, shape1 = p*n, shape2 = (1-p)*n)*n
sample.beta.p <- sample.beta.k/n
## population standard error/confidence interval
true.beta.p.conf.02.5 <- sample.beta.p-1.96*true.p.se
true.beta.p.conf.97.5 <- sample.beta.p+1.96*true.p.se
true.beta.theta_in_conf <- true.beta.p.conf.02.5 < p & true.beta.p.conf.97.5 > p
## sample standard error/confidence interval
sample.beta.p.se <- sqrt(sample.beta.p*(1-sample.beta.p)/n)
sample.beta.p.conf.02.5 <- sample.beta.p-1.96*sample.beta.p.se
sample.beta.p.conf.97.5 <- sample.beta.p+1.96*sample.beta.p.se
sample.beta.theta_in_conf <- sample.beta.p.conf.02.5 < p & sample.beta.p.conf.97.5 > p
# First one-time sample confidence intervals
one_time.sample.p.se <- sqrt((k/n)*(1-k/n)/n)
one_time_sample.conf_02.5 <- (k/n)-1.96*one_time.sample.p.se
one_time_sample.conf_97.5 <- (k/n)+1.96*one_time.sample.p.se
# One time sample either contains true value of theta or not
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = rep(c(one_time_sample.conf_02.5, one_time_sample.conf_97.5), each = 3), y = c(1,-1,0,0,-1,1), name = 'Confidence interval') %>%
add_trace(x = p, y = 0, mode = 'markers', name = 'True value', marker = list(size=50, symbol = 'x')) %>%
layout(showlegend = F
, yaxis = list(range = c(-2, 2), zeroline = F, showticklabels = F)
, xaxis = list(range = c(one_time_sample.conf_02.5 - 0.1, one_time_sample.conf_97.5 + 0.1))
, title = "One-time sample confidence interval either contains true value of theta or not")
# Cumulative confidence intervals contain 95% of the time
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = 1:num_repeated_samples
, y = cumsum(true.beta.theta_in_conf)/cumsum(rep(1,num_repeated_samples))
, name = 'Cumulative mean with sampling') %>%
layout(showlegend = F
#, yaxis = list(range = c(0, 1))
, title = "Cumulative confidence intervals tends to contain p 95% of the time")
NA
In order to obtain these results, certain conditions have to be met, including:
- The randomly sampled observations are independent, so observing any one value does not have an impact on what subsequent values we observe might be. In our example, flipping a head once does not impact the likelihood of flipping it again. (If running an experiment in practice, this might mean that our population is sufficiently large when compared to our sample that we don’t need to be concerned with replacement. Another thing to watch out for is network effects - imagine an airline increases price of seats as they sell. Say we want to experiment in offering some customers a special offer for airline tickets, our variant, and some not, our control: the customers with the special offer might be more likely to buy, and this will shorten the supply, increasing the price for those without the special offer, and decreasing their likelihood to buy).
- Any sampled observations are identically distributed to the population (e.g. if we take our sample from the USA, they might have a different propensity to watch TV than the UK.)
- Because it is a random sample, the values observed are characterised by a probability distribution associated with \(\theta\). (e.g. we don’t know what the number of heads oberved will be before sampling, but the likelihood of what we observe is pre-determined through its associated probability distribution with \(\theta\))
Okay, so what exactly does a Bayesian approach mean?
Bayesian inference is broadly similar to frequentist inference. The key difference though is that, under a Bayesian approach, the true value of \(\theta\) is treated as a random variable, rather than a fixed constant.
So, for example, we might believe that in our economy, \(90\)% of coins are fair, and \(10\)% of coins are biased, with biased coins flipping heads \(20\)% of the time.
Under the guise of being frequentists previously, we had no prior belief as to what \(\theta\) would be: we only made an educated guess based on the 2 heads we observed. We believed that there is one fixed value of the true \(\theta\), and that there was only randomness associated with sampling, so we created a confidence interval to portray this.
Now, as bayesians, we are also incorporating our prior beliefs as to what \(\theta\) is - that it is either fair or biased. We believe that there is not just random error associated in sampling - we also treat \(\theta\) as an additional random variable, since we don’t know whether our coin is fair or biased either, and fair coins will have a different sample mean distribution than biased ones.
fair_coin_k_prob <- binomial_probability(k, n, p)
biased_coin_k_prob <- binomial_probability(k, n, k/n)
Given that we observe 2 heads, the likelihood of this occuring if the coin is fair is \(4.39%\)%, and \(30.2%\)% if the coin is biased. In the absence of informative prior information then, it might appear that the coin is more likely to be biased.
However, we also need to take into account that \(90\)% of coins in the population are fair, so even before observing 2 heads, we have some belief about whether the coin is fair or biased (i.e. the probability distribution associated with the random variable \(\theta\)).
fair_coin_prob <- (fair_coin_k_prob * 0.9)/((fair_coin_k_prob * 0.9) + (biased_coin_k_prob * 0.1))
biased_coin_prob <- (biased_coin_k_prob * 0.1)/((fair_coin_k_prob * 0.9) + (biased_coin_k_prob * 0.1))
# data.frame(
# matrix(data = c(binomial_probability(2,10,0.5)*0.9 # p(fair, 2 heads)
# , (1-binomial_probability(2,10,0.5))*0.9 # p(fair, not 2 heads)
# , 0.9 # p(fair)
# , binomial_probability(2,10,0.2)*0.1 # biased, 2 heads
# , (1-binomial_probability(2,10,0.2))*0.1 # biased, not 2 heads
# , 0.1
# , binomial_probability(2,10,0.5)*0.9 + binomial_probability(2,10,0.2)*0.1
# , (1-binomial_probability(2,10,0.5))*0.9 + (1-binomial_probability(2,10,0.2))*0.1
# , 1
# )
# , nrow = 3
# , dimnames = list(c('Flip 2 heads', 'Not flip 2 heads', 'Total')
# , c('Fair', 'Biased', 'Total'))
# )
# )
..and so we can find the likelihood we got a fair coin, given the fact we observed 2 heads:
\[
P(\text{fair}|H=2)
=\frac{P(\text{H=2 and fair})}{P(\text{H=2 and fair})+P(\text{H=2 and biased})}
=\frac{P(\text{H=2|fair}) \times P(\text{fair})}{P(\text{H=2})}
\]
\[
P(\text{fair}|H=2)
=\frac{0.0439 \times 0.9}{0.0439 + 0.302}=0.567
\]
\[
P(\text{biased}|H=2)
=\frac{P(\text{H=2 and biased})}{P(\text{H=2 and fair})+P(\text{H=2 and biased})}
=\frac{P(\text{H=2|biased}) \times P(\text{biased})}{P(\text{H=2})}
\] \[
P(\text{biased}|H=2)
=\frac{0.302 \times 0.1}{0.0439 + 0.302}=0.433
\]
In other words, our prior belief (before sampling and observing any data) was that the likelihood of our coin having \(\theta\) equal to \(0.125\) was \(90\%\), and the likelihood of it having theta equal to \(0.2\) was \(10\%\). After observing 2 heads, we update our beliefs, so that the likelihood of the probability of our coin flipping heads (\(\theta\)) being equal to \(0.5\) is now equal to \(56.7\%\), and of it being equal to \(0.2\) being \(43.3\%\)
It is this incorporation of prior data that is either seen as Bayesian’s biggest advantage or pitfall. On the one hand, experiments are not abstract devices, and some knowledge about the process being investigated before obtaining the data is known and arguably should be incorporated. On the other, incorporating subjective opinions, particularly strong ones, may mean that you do not learn the true values you are trying to derive. Bayesian is thus analysis that uses a set of observations to change opinion rather than as a means to determine ultimate truth.
To help describe bayesian analysis, the following terms are often used:
- Prior distribution: \(Pr(\theta)\) - represents existing belief about \(\theta\) (Represents what was thought before seeing the data). For example, in the binomial coin example above, we have prior knowledge that 90% of coins in our economy are fair, so \(P(\theta)=P(Biased)=0.1\)
- Evidence: \(X\) - what we just observed (\(2\) heads)
- Marginal probability: \(Pr(X)\) - the total probability of the data across all possible values of the parameter \(\theta\). It doesn’t actually depend on \(\theta\) and isoften referred to as the proportionality factor/normalising constant (it makes sure all the scenarios are modelled. For example, \(P(H=2) = P(H=2|Fair) \times P(Fair) + P(H=2|Biased) \times P(Biased)\))
- Likelihood function: \(Pr(X|\theta)\) - the probability of \(\theta\) given the data observed (Represents the new data available). For example, \(P(H=2|Biased)=0.3019899\)
- Joint probability density function: \(Pr(X,\theta)=Pr((X|\theta).Pr(\theta)\) - used to modify prior beliefs through Bayes Theorem
- Posterior distribution: \(Pr(\theta|X)\) - the posterior density represents the knowledge about the model parameters after observing the data (Represents what is now thought given both prior data and data just obtained)
- Conjugancy: occurs when the posterior distribution is in the same family of probability density functions as the prior belief, but with new parameter values (updated to reflect what has been learned from the data). The posterior comes from the same family as the prior, rather than the data’s distribution.
And thus, we can then describe Bayes Theorem:
\[
P(\theta|X) =\frac{P(X|\theta) \times P(\theta)}{P(X|\theta) \times P(\theta) + P(X|\theta') \times P(\theta')} =\frac{P(X|\theta) \times P(\theta)}{P(X)}
\]
Okay - the example above might not quite be a fair comparison, since the Bayesian example had quite a strong prior: that there were only two possible values for theta, and that 90% of the time it is 0.5.
A more ‘objective’ prior that is a fairer comparison to the frequentist example is to give all values of theta have an equal likelihood - in other words, a uniform distribution. We can model this using a beta distribution. Going forwards too, let’s make this more generic, and term the number of heads observed in the sample as \(k\).
A quick introduction to the beta distribution: it can model lots of different functional forms using \(a\) and \(b\) as parameters, by inputting them into the following function:
\[
\text{Beta}[a,b] \sim \theta^{a-1}\times(1-\theta)^{b-1}
\]
So - if we want to create a uniform distribution for our prior, we can model this using a beta distribution by setting \(a\) and \(b\) to both equal to 1
\[
p(\theta) \sim \text{Beta}[1,1] \sim \theta^{1-1}\times(1-\theta)^{1-1}=\theta^{0}\times(1-\theta)^{0}= 1 \text{ (for all values of }\theta)
\]
And we can model our likelihood using the binomial function
\[
p(X| \theta) = p(\text{H=}k| \theta) = \text{Binom}(n,p) \sim \theta^k\times(1-\theta)^{n-k}
\]
And finally - the posterior is proportional to the prior multiplied by the likelihood:
\[
p(\theta) \times p(X| \theta) \sim [\theta^{a-1}\times(1-\theta)^{b-1}] \times [\theta^k\times(1-\theta)^{n-k}] = \theta^{a-1+k}\times(1-\theta)^{b-1+n-k}
\]
Which we can purely parametize in a beta distribution (you can see that, the stronger the prior - and hence the larger a and b - the smaller the impact new evidence k and n has on the posterior distribution):
\[
\theta^{a-1+k}\times(1-\theta)^{b-1+n-k} \sim \text{Beta}[a+k,b+n-k]
\]
(Note this is an approximation - the actual equality is specified later, as an example of conjugancy)
gamma_function <- function(n) {
return(factorial(n-1))
}
beta_probability <- function(theta,a,b) {
numerator <- ((theta)^(a-1))*((1-theta)^(b-1))
denominator <- (gamma_function(a)*gamma_function(b))/gamma_function(a+b)
return(numerator/denominator)
}
a <- 1
b <- 1
# uniform distribution
# prior <- dbeta(x = x, shape1 = 1, shape2 = 1)
x <- seq(0, 1, length=100+1)
prior <- sapply(x, FUN = function(theta) {beta_probability(theta,a,b)})
# binomial distribution
likelihood_f.binom <- sapply(x, FUN = function(theta) {binomial_probability(k,n,theta)})
likelihood_f.binom.int <- likelihood_f.binom
likelihood_f.binom.int[round(x*n,0) != x*n] <- NA
# beta distribution
likelihood_f.beta <- sapply(x, FUN = function(theta) {beta_probability(theta,k+1,n-k+1)*1/(n+1)})
posterior <- sapply(x, FUN = function(theta) {beta_probability(theta,a+k+1,b+n-k+1)*1/(n+1)})
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = x, y = prior/sum(prior), name = 'Prior: Uniform = Beta(1,1)') %>%
add_trace(x = x, y = likelihood_f.binom.int, name = 'Likelihood: ~ Binom(k=2,p=theta,n)', mode = 'markers') %>%
add_trace(x = x, y = likelihood_f.beta, name = 'Likelihood: ~ Beta(p=theta,k,n-k)') %>%
add_trace(x = x, y = posterior, name = 'Posterior: ~ Beta(a+k,b+n-k)') %>%
layout(xaxis = list(title = 'Theta'))
As you can see, with a very ‘objective’ prior, the Bayesian posterior is very similar to the result derived from the frequentist evidence-only distribution (the Bayesian likelihood function).
Note here that this a good example of conjugancy - see the section below on what that means exactly.
In the two Bayesian examples above though, we either had a very weak prior (the uniform distribution) or a very strong prior (only two available values for theta, and 90% likelihood the coin is fair). Bayesian tends to most valuable where both the new data and past prior have more equal influence, and the posterior forming a distribution that sits somewhere between that estimated by the prior and likelihood function:
So - let’s say the last coin we tried flipping 10 times got heads 1.25 times (our prior) and the new coin flipped heads 2 times (our new evidence). We can then get the following equations:
\[
\text{Prior: } \text{Beta}[k_{1},n_{1}-k_{1}] = \text{Beta}[5,10-5] = \text{Beta}[5,5]
\] \[
\text{Likelihood: } \text{Beta}[k_{2},n_{2}-k_{2}] = \text{Beta}[2,10-2] = \text{Beta}[2,8]
\]
\[
\text{Posterior: } \text{Beta}[k_{1}+k_{2},n_{1}-k_{1}+n_{2}-k_{2}] = \text{Beta}[5 + 2,5 + 8] = \text{Beta}[7,13]
\]
# prior <- sapply(x, FUN = function(theta) {beta_probability(theta,k1+1,n1-k1+1)/(n1+1)})
# likelihood_f <- sapply(x, FUN = function(theta) {beta_probability(theta,k2+1,n2-k2+1)/(n2+1)})
# posterior <- sapply(x, FUN = function(theta) {beta_probability(theta,k1+k2+2,n1-k1+1+n2-k2+1)/(n1+n2+2)})
# prior <- dbeta(x, k1+1, n1-k1+1)/(n1+1)
# likelihood_f <- dbeta(x, k2+1, n2-k2+1)/(n2+1)
# posterior <- dbeta(x, k1+k2+1, n1-k1+n2-k2+1)/(n1+n2+1)
prior <- dbeta(x, k1, n1-k1)
likelihood_f <- dbeta(x, k2, n2-k2)
posterior <- dbeta(x, k1+k2, n1-k1+n2-k2)
plot_ly(type = 'scatter', mode = 'lines') %>%
add_trace(x = x, y = prior, name = 'Prior belief: Horse') %>%
add_trace(x = x, y = likelihood_f, name = 'Likelihood (New data): Donkey') %>%
add_trace(x = x, y = posterior, name = 'Posterior Belief: Mule') %>%
layout(title = "Updating Prior Beliefs")
The posterior curve is both taller and narrow than both the distributions estimated from the prior and the likelihood functions. This is because, by including both prior data and new evidence, our sample size has increased, so this reflects greater confidence that the observed number of heads,conditioned by the probability distribution of \(\theta\), will lie within a smaller interval.
Which leads on to Bayesian Credible intervals - the Bayesian equivalent to frequentist’s confidence intervals. Because Bayesian estimates distributions rather than fixed values, credible intervals are arguably more intuitive than confidence intervals: they reflect the a (95%) probability that of here the value generated by the random variable theta will fall within the range (rather than the frequentist interpretation that the true value will fall within the confidence interval 95% of the time).
Like a confidence interval, a credible interval is symmetric around the mean, and spans the x-axis enough to cover 95% of the area under the probability distribution curve. And that is good if the posterior distribution is also symmetric - but as can be seen in our example above, that is not necessarily the case, where the posterior is skewed.
If the distribution is skewed then, it could be better to compute the region of highest posterior density (HPD) - which by definition will be the narrowest interval across the potential values for theta, but cover 95% of the area under the probability curve. In other words, we still maintain the same 95% probability of theta lying within the region, but the region is the narrowest it possibly can be.
So to do this, we want to find the interval between \(\theta_{low}\) and \(\theta_{high}\) such at:
\[
\int_{\theta_{low}}^{\theta_{high}} p(\theta|x) d\theta= 1-\alpha
\]
But finding this can be tricky, particularly with computing closed intervals. The code below shows a brute force solution. The way to think about this is as follows: * Credible intervals: Given the mean of the distribution, expand the range outwards equally until 95% of the area under the curve is captured. * Highest posterior density: Imagine a horizontal line moving slowly towards the x axis, intercepting the distribution twice. Once the
(NOTE THE GRAPH BELOW IS WRONG, NEEDS FIXING)
find_binomial_credible_interval <- function(k, n, p, learning_rate = 0.5, initial_width = 0.1, criterion = 0.1, max_iterations = 1000, precision = 4) {
bit <- initial_width/2 # amount to push away from mean
for(i in 1:max_iterations) {
amount <- pbeta(p+bit, k+1, n-k+1) - pbeta(p-bit, k+1, n-k+1) # sum the auc between p-bit and p+bit
bit <- bit - learning_rate*(amount - (1-criterion)) # decrease if auc > 0.95 or increase if auc < 0.85
if(abs(amount - (1-criterion)) < 1/(10^precision)) {
break()
}
}
return(c(p-bit,p+bit))
}
find_binomial_highest_start_point <- function(precision = 4,k,n) {
x <- seq(0,1,10^-precision)
pdf <- dbeta(x,k,n-k)
return(x[max(pdf) == pdf])
}
find_binomial_hpd <- function(k,n,criterion=0.1, initial_movement_size = 0.1, max_iterations=10^3,learning_rate = 0.005, precision = 4) {
p <- find_binomial_highest_start_point(precision,k,n)
left_loc <- p
right_loc <- p
bit <- initial_movement_size
if(residual > 0) { # need to increase width
if(pbeta(left_loc + bit, k+1, n-k+1) > pbeta(right_loc + bit, k+1, n-k+1)) { # left side pdf is higher
left_loc <- left_loc-bit # move left
} else { # right side pdf is higher
right_loc <- right_loc+bit # move right
}
} else {
if(pbeta(left_loc + bit, k+1, n-k+1) > pbeta(right_loc + bit, k+1, n-k+1)) { # left side pdf is higher
right_loc <- right_loc+bit # move right
} else { # right side pdf is higher
left_loc <- left_loc-bit # move left
}
}
residual <- (1-criterion) - (pbeta(right_loc, k+1, n-k+1)-pbeta(left_loc, k+1, n-k+1)) # difference to e.g. 0.95
if(abs(residual) < 10^-precision) {
break()
} else {
bit <- bit - learning_rate*residual
}
return(c(left_loc, right_loc))
}
credible_intervals <- find_binomial_credible_interval(k, n, p, max_iterations = 10^3, criterion = 0.1)
highest_posterior_density <- find_binomial_hpd(k,n, max_iterations = 10^3, criterion = 0.1)
Error in find_binomial_hpd(k, n, max_iterations = 10^3, criterion = 0.1) :
object 'residual' not found
Some Bayesians argue though that credible intervals and HPDs are only really something that are useful to compare to frequentist interpretations, as the distribution is already given by the posterior.
Conjugancy (beta-binomial)
Now to get geeky - you might have already noticed how eerily similar the beta distribution is to the binomial distribution from the formula - and in fact you can use the beta distribution as a continous function equivalent to the binomial function.
\[
p(\text{H=}k| \theta) \sim \theta^k\times(1-\theta)^{n-k} \sim \text{Beta}[k+1,n-k+1]
\]
Both binomial and beta likelihoods are scaled though (normalized), so that the sum of their probabilites total 1. For the beta distribution, the scaling is achieved like this:
\[
Beta[\alpha,\beta] = \theta^{\alpha-1}\times(1-\theta)^{\beta-1} \times \frac{1}{\text{B}(\alpha,\beta)}
\] Where
\[
\frac{1}{\text{B}(\alpha,\beta)} = \frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha) \times \Gamma(\beta)} = \frac{(\alpha+\beta-1)!}{(\alpha-1)! \times (\beta-1)!}
\]
So if successes \(\alpha = k+1\) and failures \(\beta = n - k + 1\), then:
\[
\frac{(\alpha+\beta-1)!}{(\alpha-1)! \times (\beta-1)!}=\frac{((k+1)+(n-k+1)-1)!}{((k+1)-1)! \times ((n-k+1)-1)!}=\frac{(n+1)!}{(k)!\times(n-k)!} =
{n+1 \choose k } = (n+1) \times {n \choose k }
\]
Now we define the binomial distribution for comparison:
\[
\text{Binom}(n,p) = {n \choose k } [\theta^{k}\times(1-\theta)^{n-k}]
\]
And thus:
\[
Beta[k+1,n-k+1] = (n+1) \times \text{Binom}(n,p)
\]
This relationship helps us combine binomial likelihoods and beta priors to create a posterior in what is called conjugancy. Conjugancy occurs when the posterior distribution is in the same family of probability density functions as the prior belief, but with new parameter values (updated to reflect what has been learned from the data). The posterior comes from the same family as the prior, rather than the data’s distribution.
All the three coin examples above were examples of conjugancy. For example, the second had a prior that was uniform, expressed as a beta distribution, whereas the likelihood function was a binomial distribution. The posterior distribution was thus beta, since it is the same family of probability density functions as the prior belief (beta), but with new parameter values learnt from the probability mass function derived from the new data. Note that the posterior did not follow a binomial distribution, but followed a beta one, since this is what the prior used. Conjugates are thus very useful in helping derive the posterior distribution.
Without conjugancy, one has to do the integral, which is often impossible to actually evaluate, and is one of the reasons bayesian was not popular in the 20th century (before computing allowed researchers to compute integrals numerically). Nowadays, sampling methods such as Markov-chain monte-carlo (MCMC) are often used to simulate the posterior distribution.
Conjugancy (gamma-poisson)
As well as the beta-binomial conjugate family, we also have the gamma-poisson conjugate family.
The poisson function is specified as:
\[
P(X=k)=\frac{\lambda^{k}}{k!}e^{-\lambda} \text{ for } k=0,1,...,
\]
Whereas the gamma family is related to the gamma function (witk \(k,\theta\) and \(\alpha,\beta\) parameterizations listed below):
\[
f(x)=\frac{1}{\Gamma(k)\theta^k}x^{k-1}e^{-x/\theta}=\frac{\beta^{\alpha}}{\Gamma(k)}x^{\alpha-1}e^{-\beta x}
\] And hence we can see that that where \(n\) is a positive integer, and \(\theta=1\), we observe the special case that \(\Gamma(k)=(k-1)!\) so that
NEED TO WORK ON THIS BIT
\[
\frac{1}{\Gamma(k)\times\theta^k}x^{k-1}e^{-x/\theta}=
\frac{1}{(k-1)!\times1^k}x^{k-1}e^{-x/\theta}=
\frac{\lambda^{k}}{k!}e^{-\lambda}
\]
Thinking about Bayesian in terms of predicting things
There are two sources of uncertainty when building statistical models to predict things:
- Uncertainty due to the fact any future value is itself a random event, \(P(y|\theta)\) (because future events are essentially samples that have error conditioned by \(\theta\))
- Uncertainty in the parameter values which have been estimated on the basis of past data, \(P(\theta|X)\) (for example, a coefficient estimated in a regression model)
Classical models deal with point 1, making a point estimate in the future based on the ‘best’ parameters estimated from past data. This is equivalent to forming a likelihood (i.e. incorporating new data). What they don’t do though is think about point 2, that the seemingly optimum model estimated itself might be incorrect since the true values of \(\theta\) are not fixed, and this is equivalent to not building in any prior beliefs. In a way, by giving a point estimate, the models generate a false sense of precision, and the confidence intervals arounds any estimate is only predicated on the idea there is sampling randomness, rather than randomness associated with \(\theta\) itself.
In other words, classical models seek to best fit the new evidence (traditionally through maximum likelihood estimation for generalized linear models), whereas bayesian models incorporate prior beliefs as well.
Imagine then, if we want to estimate the impact of x on y to make a future prediction, we can do the following:
\[
f(y|x)= \int f(y|\theta,x)f(\theta|x) \partial(\theta)
\]
Where \(f(y|\theta,x)\) represents the modelling random sampling error as in frequentist regression (the likelihood function), and \(f(\theta|x)\) representing the error arising from \(\theta\) being a random variable rather than being treated as a fixed quantity.
Now why is it an integral? Let’s think of the coin example above where there are only two types of coins in the economy. If we want to know what is the probability we get heads, rather than the probability that we have a fair or a biased coin.
\[
P(\text{heads}|k=2)
\\ = P(\text{heads}|\text{fair},k=2) \times P(\text{fair}|k=2) + P(\text{heads}|\text{biased},k=2) \times P(\text{biased}|k=2)
\]
As before, we summarise the probability mass function relating to \(\theta\) as being 0.5 (fair) for 90% of coins in the economy, and $0.2 (biased) for 10% of these coins, which gives us the following:
\[
P(\text{heads|k=2}) \\
= \sum_{\theta}{P(\text{heads}|\theta\text{,k=2}) \times P(\theta|\text{k=2}) }
\]
And by taking into account all the possible values that theta can take, we are essentially integrating along the
\[
P(\text{heads|k=2}) = \int P(\text{heads}|\theta,k=2) \text{ }P(\theta|k=2) \text{ } \partial(\theta)
\\
\text{where }\theta =
\begin{cases}
0.2 & 10\% \text{ of the time}\\
0.5 & 90\% \text{ of the time}\\
\end{cases}
\]
NEED TO RE-WRITE EVERYTHING BELOW THIS
!!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!! !!!!!!!!!!!!!
Now because this equation is done through conjugancy, this is easy to evaluate. Another way then of looking at it for this example is by rearranging bayes theroem:
\[
P(y|X) = \frac{P(y|\theta,X) \times P(\theta|X)}{P(\theta|y,X)}
= \frac{P(\text{heads}|\text{fair},k=2) \times P(\theta|X)}{P(\theta|y,X)}
\]
$$ P(|X) = = \
$$
And hence it can be seen that to get the full probability distribution associated with getting heads, you need to assess all possible values that theta could take.
\[
P(y|X)
= \frac{P(y|\theta,X) \times P(\theta|X)}{P(\theta|y,X)}
= \frac{P(\text{heads}|\theta,k=2) \times P(\theta|k=2)}{P(\theta|\text{heads,k=2})}
\]
$$ P() = + \
$$
As before, we summarise the probability mass function relating to \(\theta\) as being 0.5 (fair) for 90% of coins in the economy, and 2 (biased) for 10% of these coins, which gives us the following:
\[
P(\text{heads|k=2}) = P(\text{heads}|\theta\text{,k=2}) \times P(\theta|\text{k=2})
\]
\[
P(\text{heads}) = P(\text{heads}|\text{fair}) \times P(\text{fair}) + P(\text{heads}|\text{biased}) \times P(\text{biased})
\]
\[
P(X,\theta|k=2) = \frac{P(\text{heads}|\theta,k=2) \times P(\theta|X)}{P(heads|k=2)}
\]
\[
P(y|X) = \frac{P(y|\theta,X) \times P(\theta|X)}{P(\theta|y,X)}
\]
Let’s say we believe the sampling error of y to follow a normal distribution, conditioned by \(\theta\) (capturing the first source of uncertainty), which we would normally solve through MLE:
\[
f(y|\theta) = \frac{1}{\sigma\sqrt{2\pi}}\text{exp}(\frac{(y-\theta)^2}{2\sigma^2})
\] \[
f(y|\theta,X) = \frac{1}{\sigma\sqrt{2\pi}}\text{exp}(\frac{(y-X\beta)^2}{2\sigma^2})
\]
Then we just need to derive \(f(\theta|x)\) in order to make a future prediction through bayes (and this term captures the error associated with our estimation of theta from the exogenous variables).
Now for frequentists, the pdf \(f(\theta|x)\) is equal to 1 at the true value of theta, and zero elsewhere, as theta is fixed (so there is only one perfect value).
Though for Bayesians, the pdf is conditioned by prior beliefs about \(\theta\). These are represented as a posterior approximated from the product of the likelihood of observing the exogenous variables given \(\theta\), and the prior beliefs associated with \(\theta\):
\[
f(\theta|x) \sim f(\theta) \times f(x|\theta)
\] To capture the randomness of the \(\theta\), we might also believe our prior \(f(\theta)\) follows a normal distribution, but with mean \(E(X)=b\) and variance \(Var(X)=d^2\). As such, the distribution thus described is \(X \sim N(b,d^2)\)
Then the prior can be derived from the normal pdf \(x\):
\[
f(\theta) = \frac{1}{d\sqrt{2\pi}}\text{exp}(\frac{(\theta-b)^2}{2d^2})
\]
Now let’s take the observed data \(x=(x_1,x_3,...,x_n)\) and treat it as a random sample of size \(n\) of a random variable \(X\) with mean \(E(X)=\theta\) and variance \(Var(X)=\sigma^2\), and follows a normal distribution thus described as \(X \sim N(\theta,\sigma^2)\)
Then the likelihood for every obervation \(x_i\) from the whole sample \(x\):
\[
f(x|\theta) = \prod_{i=1}^{n} f(x_i|\theta) = \prod_{i=1}^{n} \frac{1}{\sigma\sqrt{2\pi}}exp(\frac{(x_i-\theta)^2}{2\sigma^2})
\]
LS0tCnRpdGxlOiAiQmF5ZXNpYW4gU3RhdGlzdGljcyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUKICAgIHNtYXJ0OiBmYWxzZQogIGh0bWxfZG9jdW1lbnQ6IGRlZmF1bHQKICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQKLS0tCgpgYGB7ciBzZXR1cCwgZWNobyA9IEZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoCglmaWcuaGVpZ2h0ID0gNywKCWZpZy53aWR0aCA9IDEwLAoJbWVzc2FnZSA9IEZBTFNFLAoJd2FybmluZyA9IEZBTFNFCikKcmVxdWlyZShwbG90bHkpCnJlcXVpcmUoc2NhbGVzKQpgYGAKCipBIEJheWVzaWFuIGlzIG9uZSB3aG8sIHZhZ3VlbHkgZXhwZWN0aW5nIGEgaG9yc2UsIGFuZCBjYXRjaGluZyBhIGdsaW1wc2Ugb2YgYSBkb25rZXksIHN0cm9uZ2x5IGJlbGlldmVzIGhlIGhhcyBzZWVuIGEgbXVsZSoKCldoeSBtaWdodCBzb21lb25lIHVzZSBCYXllc2lhbiByYXRoZXIgdGhhbiB0cmFkaXRpb25hbCBmcmVxdWVudGlzdD8KCiogSWYgdGhleSBoYXZlIHByaW9yIGJlbGllZnMgYXMgdG8gdGhlIHRydXRoIGJlZm9yZSBhbiBleHBlcmltZW50IGlzIGNvbmR1Y3RlZAoqIElmIHlvdSB3YW50IHRvIHByZWRpY3QgaG93IHRoZSBkaXN0cmlidXRpb24gb2YgYSBwb3B1bGF0aW9uIG1pZ2h0IGNoYW5nZSwgcmF0aGVyIHRoYW4gYSBwb2ludCBlc3RpbWF0ZS4gRm9yIGV4YW1wbGUsIHRyYWRpdGlvbmFsbHksIHdlIG1pZ2h0IHRyeSBhbmQgcHJlZGljdCB0aGUgbWVhbiBudW1iZXIgb2YgcGVvcGxlIHdobyBjaG9vc2UgdG8gb3JkZXIgYWZ0ZXIgZ29pbmcgb24gb3VyIHdlYnNpdGUuIAoKIyMgUXVpY2sgcmVjYXAgb2YgdGhlICdDbGFzc2ljYWwgQXBwcm9hY2gnICgnRnJlcXVlbnRpc3QnKQoKYGBge3J9CnNldC5zZWVkKDApCnAgPC0gMC41Cm4gPC0gMTAKYGBgCgpMZXQncyBzYXkgd2UgaGF2ZSBhIGNvaW4sIGFuZCB3ZSB3YW50IHRvIGtub3cgdGhlIHByb2JhYmlsaXR5IHRoYXQgd2UgZmxpcCBoZWFkcy4gRnJlcXVlbnRpc3RzIGFzc3VtZSB0aGF0IHRoZXJlIGlzIG9ubHkgb25lIHRydWUsIGZpeGVkLCB1bmtub3duIHByb2JhYmlsaXR5IHRoYXQgdGhlIGNvaW4geWllbGRzIGhlYWRzLiBGb3IgZWFzZSBvZiBub3RhdGlvbiwgbGV0J3MgY2FsbCB0aGUgY29uc3RhbnQgcGFyYW1ldGVyICRwKFx0ZXh0e2hlYWR9KSA9IFx0aGV0YSQuCgpUbyB0cnkgYW5kIGRpc2NvdmVyIHRoZSB0cnVlIHByb2JhYmlsaXR5IG9mIGdldHRpbmcgYSBoZWFkLCB3ZSBmbGlwIHRoZSBjb2luIGByIG5gIHRpbWVzLCBhbmQgY291bnQgdGhlIG51bWJlciBvZiBoZWFkcyB0byBlc3RpbWF0ZSB0aGUgcHJvYmFiaWxpdHkuIEZyZXF1ZW50aXN0cyBiZWxpZXZlIHRoYXQgaWYgd2UgcmVwZWF0ZWQgdGhpcyBzYW1wbGluZyBwcm9jZWVkdXJlIG9mIDEwIGZsaXBzIG1hbnksIG1hbnkgdGltZXMsIHdlIHNob3VsZCBleHBlY3QgdGhlIGF2ZXJhZ2UgYWNyb3NzIGFsbCBvZiBvdXIgc2FtcGxlcyB0byBiZSByZWZsZWN0aXZlIG9mIHRoZSB0cnVlIHBvcHVsYXRpb24gdmFsdWUgKGhlbmNlIHdoeSBpdCBpcyBjYWxsZWQgJ2ZyZXF1ZW50aXN0JykuIAoKYGBgIHtyLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9N30KIyBDcmVhdGUgcmVwZWF0ZWQgc2FtcGxlcwpudW1fcmVwZWF0ZWRfc2FtcGxlcyA8LSAxMF4zCnJlcGVhdGVkX3NhbXBsZXMgPC0gcmJpbm9tKG4gPSBudW1fcmVwZWF0ZWRfc2FtcGxlcywgc2l6ZSA9IG4sIHByb2IgPSBwKQpyZXBlYXRlZF9zYW1wbGVzLmN1bV9wX21lYW4gPC0gY3Vtc3VtKHJlcGVhdGVkX3NhbXBsZXMpL2N1bXN1bShyZXAobiwgbnVtX3JlcGVhdGVkX3NhbXBsZXMpKQoKIyBDdW11bGF0aXZlIG1lYW4gdGVuZHMgdG8gcApwbG90X2x5KHR5cGUgPSAnc2NhdHRlcicsIG1vZGUgPSAnbGluZXMnKSAlPiUKICBhZGRfdHJhY2UoeCA9IDE6bGVuZ3RoKHJlcGVhdGVkX3NhbXBsZXMpLCB5ID0gcmVwZWF0ZWRfc2FtcGxlcy5jdW1fcF9tZWFuLCBuYW1lID0gJ0N1bXVsYXRpdmUgbWVhbiB3aXRoIHNhbXBsaW5nJykgJT4lCiAgbGF5b3V0KHNob3dsZWdlbmQgPSBGCiAgICAgICAgICwgeWF4aXMgPSBsaXN0KHJhbmdlID0gYygwLCAxKSkKICAgICAgICAgLCB0aXRsZSA9ICJDdW11bGF0aXZlIHNhbXBsZSBtZWFucyB0ZW5kcyB0byB0cnVlIHAiKSAjICwgCmBgYAoKYGBgIHtyLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9N30KayA8LSByb3VuZChuKnAqMC41LDApICMgbWFrZSB1cCBmYWtlIGsgdGhhdCBpcyAndW5saWtlbHknCnNhbXBsZV9tZWFuIDwtIGsvbgoKYmlub21pYWxfcHJvYmFiaWxpdHkgPC0gZnVuY3Rpb24oaywgbiwgcCkgewogIG5fY2hvb3NlX2sgPC0gZmFjdG9yaWFsKG4pLyhmYWN0b3JpYWwoaykqZmFjdG9yaWFsKG4taykpCiAgIyBOT1RFIC0gZXF1aXZhbGVudCB0byBnYW1tYV9mdW5jdGlvbihrK24taykvKGdhbW1hX2Z1bmN0aW9uKGspKmdhbW1hX2Z1bmN0aW9uKG4tayksIG9yIDEvQihrLG4taykKICBwcm9iX3NhbXBsZSA8LSBuX2Nob29zZV9rKihwKV5rKigxLXApXihuLWspCiAgcmV0dXJuKHByb2Jfc2FtcGxlKQp9CgprX2hlYWRzX21heHByb2IgPC0gcm91bmQoYmlub21pYWxfcHJvYmFiaWxpdHkoayxuLGsvbiksNCkqMTAwCmtfaGVhZHNfYWN0cHJvYiA8LSByb3VuZChiaW5vbWlhbF9wcm9iYWJpbGl0eShrLG4scCksNCkqMTAwCm5wX2hlYWRzX2FjdHByb2IgPC0gcm91bmQoYmlub21pYWxfcHJvYmFiaWxpdHkobipwLG4scCksNCkqMTAwCgpgYGAKCkJ1dCBpbiB0aGUgcmVhbCB3b3JsZCwgaXQncyBub3QgcG9zc2libGUgdG8gdGFrZSBsb3RzIG9mIHNhbXBsZXMgb3ZlciBhbmQgb3ZlciBhZ2FpbiAtIGFuZCB3ZSBnZW5lcmFsbHkganVzdCB0YWtlIG9uZS4gVGFraW5nIGEgc2FtcGxlIG9uZSB0aW1lLCB3ZSBtaWdodCBvYnNlcnZlIGByIGtgIGhlYWRzLiBUaGlzIGlzIGVxdWl2YWxlbnQgdG8gY3JlYXRpbmcgYSBzYW1wbGUgb2Ygc2l6ZSAkYHIgbmAkIGFuZCBvYnNlcnZpbmcgYSBtZWFuIHByb2JhYmlsaXR5IG9mICRgciBzYW1wbGVfbWVhbmAkLgoKV2UgZG9uJ3Qga25vdyB3aGF0IHRoZSB0cnVlIHByb2JhYmlsaXR5IG9mIGZsaXBwaW5nIGhlYWRzIGlzICgkXHRoZXRhJCksIGJ1dCB3ZSBjYW4gcGxvdCB0aGUgbGlrZWxpaG9vZCBvZiBvYnNlcnZpbmcgYHIga2AgaGVhZHMgZm9yIGV2ZXJ5IHBvc3NpYmxlICRcdGhldGEkIHRoZSBjb2luIG1pZ2h0IGJlLiBPbiB0aGUgbGVmdCBncmFwaCBiZWxvdywgZm9yIGV2ZXJ5IHBvc3NpYmxlIHZhbHVlIHRoYXQgdGhlIHByb2JhYmlsaXR5IG9mIGZsaXBwaW5nIGhlYWRzIGNvdWxkIGJlIG9uIHRoZSB4IGF4aXMgKHNvbWV3aGVyZSBiZXR3ZWVuIDAgYW5kIDEpLCB0aGUgbGlrZWxpaG9vZCBvZiBvYnNlcnZpbmcgJGByIGtgJCBoZWFkcyBpcyBwbG90dGVkIG9uIHRoZSB5IGF4aXMsIGdpdmluZyB0aGUgb3JhbmdlIGxpbmUuIEZvciBleGFtcGxlLCB0aGUgbGlrZWxpaG9vZCBvZiBvYnNlcnZpbmcgJGByIGtgJCBoZWFkcyBpZiB0aGUgcHJvYmFibGl0eSBvZiBmbGlwcGluZyBoZWFkcyBpcyAkYHIgay9uYCQgaXMgJGByIGtfaGVhZHNfbWF4cHJvYmBcJWAkLiBJZiB0aGUgcHJvYmFibGl0eSBvZiBmbGlwcGluZyBoZWFkcyBpcyBhY3R1YWxseSAkYHIgcGAkLCB0aGVuIHRoZSBsaWtlbGlob29kIG9mIGZsaXBwaW5nIGByIGtgIGhlYWRzIGluIG91ciBzYW1wbGUgaXMgb25seSAkYHIga19oZWFkc19hY3Rwcm9iYFwlJC4gCgpJdCBhcHBlYXJzIG1vc3QgcHJvYmFibGUgZnJvbSBvdXIgc2FtcGxlIHRoZW4gdGhhdCBvdXIgdHJ1ZSBwcm9iYWJpbGl0eSBpcyBpbmRlZWQgYHIgc2FtcGxlX21lYW5gIC0gdGhlIG1vc3QgbGlrZWx5IHByb2JhYmlsaXR5IGlzIHdoYXQgd2Ugb2JzZXJ2ZSBhcyB0aGUgbWVhbiBpbiBvdXIgc2FtcGxlICh0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRpb24gaXMgYCByc2FtcGxlX21lYW5gKS4gVGh1cywgYSBmcmVxdWVudGlzdCB3b3VsZCBjb25jbHVkZSB0aGF0IHRoZSBtb3N0IGxpa2VseSB2YWx1ZSBvZiAkXHRoZXRhJCBpcyAkYHIgc2FtcGxlX21lYW5gJCwgYW5kIHRoYXQgdGhlIHRydWUgdmFsdWUgb2YgJFx0aGV0YSQgaXMgaG9wZWZ1bGx5IG5lYXIgdG8gaXQuCgpIb3dldmVyLCBkZXNwaXRlIHRyZWF0aW5nIHRoZSB0cnVlICRcdGhldGEkIGFzIGEgZml4ZWQgKG5vbi1yYW5kb20pIHZhbHVlLCBmcmVxdWVudGlzdHMgYWNrbm93bGVkZ2UgdGhlcmUgaXMgcmFuZG9tIHNhbXBsaW5nIGVycm9yLiBFdmVuIGlmIHRoZSBwcm9iYWJpbGl0eSBvZiBmbGlwcGluZyBoZWFkcyByZW1haW5pbmcgY29uc3RhbnQsIHNvbWV0aW1lcyB0aGVyZSB3aWxsIGJlIGByIGtgIGhlYWRzLCBzb21ldGltZXMgdGhlcmUgd2lsbCBiZSBgciBuYCBoZWFkcyBldGMgc2ltcGx5IGR1ZSB0byBjaGFuY2UuIFdlIGNhbiBpbGx1c3RyYXRlIHRoaXMgYnkgcGxvdHRpbmcgdGhlIGxpa2VsaWhvb2Qgb2Ygb2JzZXJ2aW5nIGRpZmZlcmVudCBudW1iZXJzIG9mIGhlYWRzIGdpdmVuIGEgZml4ZWQgdmFsdWUgb2YgJFx0aGV0YSQuIEluIHRoZSBncmFwaCBvbiB0aGUgcmlnaHQsIHRoZSBwcm9iYWJpbGl0eSBvZiBnZXR0aW5nIGRpZmZlcmVudCBudW1iZXJzIG9mIGhlYWRzIGJldHdlZW4gMCBhbmQgYHIgbmAgaXMgcGxvdHRlZCBpbiBncmVlbiBpZiB0aGUgdmFsdWUgb2YgdGhldGEgaXMgJGByIGsvbmAkLCBhbmQgYmx1ZSBpZiB0aGUgcHJvYmFiaWxpdHkgaXMgJGByIHBgJC4KCkluIHRoaXMgd2F5IHRoZW4sIGRlc3BpdGUgYmVsaWV2aW5nIHRoZSBhY3R1YWwgKHBvcHVsYXRpb24pIHByb2JhYmlsaXR5ICRcdGhldGEkIHRvIGJlIGZpeGVkIGF0IG9uZSB2YWx1ZSAoYW5kIGZyb20gdGhlIHNhbXBsZSwgdGhlIG1vc3QgcHJvYmFibGUgYmVpbmcgJGByIGsvbmAkKSwgdGhlIGdyYXBoIG9uIHRoZSByaWdodCBpbGx1c3RyYXRlcyBob3cgZnJlcXVlbnRpc3RzIGJlbGlldmUgdGhhdCB0aGUgbnVtYmVyIG9mIGhlYWRzIG9ic2VydmVkIGlzIGEgcmFuZG9tIHZhcmlhYmxlIChjb25kaXRpb25lZCBieSAkXHRoZXRhJCkuIEJ5IHJhbmRvbSB2YXJpYWJsZSwgdGhpcyBtZWFucyB0aGF0IHRoZSBudW1iZXIgb2YgaGVhZHMgY291bGQgYmUgbWFueSBkaWZmZXJlbnQgdmFsdWVzIGJlZm9yZSBzYW1wbGluZyAoMC1gciBuYCkgcmF0aGVyIHRoYW4gYmVpbmcgcHJlLWRldGVybWluZWQvZml4ZWQgYXMgaG93IHRoZXkgdHJlYXQgJFx0aGV0YSQuIFRoZSBsaWtlbGlob29kIG9mIG9ic2VydmluZyBhbnkgb2YgdGhlc2UgcG9zc2libGUgdmFsdWVzIGlzIGNvbmRpdGlvbmVkIGJ5IHRoZSBmaXhlZCBwcm9iYWJpbGl0eSAkXHRoZXRhJCBhcyBwZXIgdGhlIGRpc3RyaWJ1dGlvbiBvbiB0aGUgcmlnaHQgKGlmIHRoZSB0cnVlIHZhbHVlIG9mICRcdGhldGEkIGlzICRgciBwYCQsIHRoZW4gb2JzZXJ2aW5nICRgciBwKm5gJCBoZWFkcyBpbiBvdXIgc2FtcGxlIGlzIGEgbG90IG1vcmUgbGlrZWx5IHRoYW4gb2JzZXJ2aW5nICRgciBuYCQsIGFuZCBvYnNlcnZpbmcgJGByIGtgJCBoZWFkcyBpcyB2ZXJ5IHVubGlrZWx5KS4KCmBgYCB7ciwgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTd9CgojIGZvciBhbGwgdGhlIGRpZmZlcmVudCB2YWx1ZXMgb2YgdGhldGEsIHAoSD0yfM64KQp0aGV0YV9wcm9iX2tfaGVhZHMgPC0gc2FwcGx5KHNlcSgwLDEsMC4wMSksIEZVTiA9IGZ1bmN0aW9uKHApIGJpbm9taWFsX3Byb2JhYmlsaXR5KGs9ayxuPW4scD1wKSkKIyBmb3IgYWxsIHRoZSBkaWZmZXJlbnQgdmFsdWVzIG9mIG91dGNvbWUgaywgcChIPWt8zrg9MC4yKQpsaWtlbGlob29kX2VzdCA8LSBzYXBwbHkoc2VxKDAsMTAsMSksIEZVTiA9IGZ1bmN0aW9uKHMpIHtiaW5vbWlhbF9wcm9iYWJpbGl0eShrPXMsbj1uLHA9ay9uKX0pCiMgZm9yIGFsbCB0aGUgZGlmZmVyZW50IHZhbHVlcyBvZiBvdXRjb21lIGssIHAoSD1rfM64PTAuNSkKbGlrZWxpaG9vZF9hY3QgPC0gc2FwcGx5KHNlcSgwLDEwLDEpLCBGVU4gPSBmdW5jdGlvbihzKSB7Ymlub21pYWxfcHJvYmFiaWxpdHkoaz1zLG49bixwPXApfSkKCgpzdWJwbG90KAogIHBsb3RfbHkodHlwZSA9ICdzY2F0dGVyJywgbW9kZSA9ICdsaW5lcycpICU+JQogICAgYWRkX3RyYWNlKHggPSBzZXEoMCwxLDAuMDEpLCB5ID0gdGhldGFfcHJvYl9rX2hlYWRzLCBuYW1lID0gcGFzdGUwKCdQKEg9JyxrLCd8zrgpJykpICU+JQogICAgbGF5b3V0KHhheGlzID0gbGlzdCh0aXRsZSA9ICfOuCcpKQogICwgcGxvdF9seSh0eXBlID0gJ3NjYXR0ZXInLCBtb2RlID0gJ2xpbmVzK21hcmtlcnMnKSAlPiUKICAgIGFkZF90cmFjZSh4ID0gc2VxKDAsMTAsMSksIHkgPSBsaWtlbGlob29kX2VzdCwgbmFtZSA9IHBhc3RlMCgncChIPWt8zrg9JyxrL24sJyknKSkgJT4lCiAgICBhZGRfdHJhY2UoeCA9IHNlcSgwLDEwLDEpLCB5ID0gbGlrZWxpaG9vZF9hY3QsIG5hbWUgPSBwYXN0ZTAoJ3AoSD1rfM64PScscCwnKScpKSAlPiUKICAgIGxheW91dCh4YXhpcyA9IGxpc3QodGl0bGUgPSAnIyBoZWFkcycpKQogICwgc2hhcmVZID0gVAogICwgbnJvd3MgPSAxKQoKIyAKIyBwbG90X2x5KHR5cGUgPSAnc2NhdHRlcicsIG1vZGUgPSAnbGluZXMnKSAlPiUKIyAgIGFkZF90cmFjZSh4ID0geCwgeSA9IGxpa2VsaWhvb2RfZXN0LCBuYW1lID0gJ0VzdGltYXRlZCBmcm9tIHNhbXBsZScpICU+JQojICAgYWRkX3RyYWNlKHggPSB4LCB5ID0gbGlrZWxpaG9vZF9hY3QsIG5hbWUgPSAnQWN0dWFsIGxpa2VsaWhvb2QnKSAlPiUKIyAgIGxheW91dCh0aXRsZSA9ICJMaWtlbGlob29kIGZ1bmN0aW9uOiBYIH4gQmlub20obixwKSIKIyAgICAgICAgICAsIHhheGlzID0gbGlzdCh0aXRsZSA9ICd0aGV0YScpCiMgICAgICAgICAgLCB5YXhpcyA9IGxpc3QodGl0bGUgPSAnbGlrZWxpaG9vZCcpKQpgYGAKCkhlbmNlLCB0byBhY2tub3dsZWRnZSB0aGF0IHRoZXJlIGlzIHJhbmRvbW5lc3MgYXNzb2NpYXRlZCB3aXRoIHRoaXMgc2FtcGxlIG1lYW4sIGZyZXF1ZW50aXN0cyBjb25zdHJ1Y3QgY29uZmlkZW5jZSBpbnRlcnZhbHMuIEFnYWluIHRvIGZvbGxvdyB0aGUgZnJlcXVlbnRpc3QgaW50ZXJwcmV0YXRpb24sIGEgOTUlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgbWVhbnMgdGhhdCwgaWYgdGhlIHNhbXBsaW5nIHByb2NlZWR1cmUgd2FzIHJlcGVhdGVkIG1hbnksIG1hbnkgdGltZXMsIHRoYXQgOTUlIG9mIHRoZSB0aW1lIHRoZSB0cnVlIHZhbHVlIG9mICRcdGhldGEkIHdvdWxkIGZhbGwgd2l0aGluIHRoZSBjb25maWRlbmNlIGludGVydmFsLgoqKE51YW5jZWQgbm90ZSAtIHRoaXMgaXMgbm90IHRoZSBzYW1lIGFzIHNheWluZyB0aGF0LCBpbiBvbmUgc2FtcGxlLCB0aGVyZSBpcyBhIDk1JSBjaGFuY2UgdGhhdCB0aGUgdHJ1ZSB2YWx1ZSBvZiAkXHRoZXRhJCBsaWVzIHdpdGhpbiBpdC4gVGhpcyBpcyBiZWNhdXNlICRcdGhldGEkIGlzIGEgZml4ZWQgdmFsdWUsIG5vdCBhIHJhbmRvbSB2YXJpYWJsZSwgc28gaXQgZWl0aGVyIGZhbGxzIHdpdGhpbiB0aGUgc2FtcGxlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgb3Igbm90LikqCgpgYGAge3IsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD03fQoKdHJ1ZS5wLnNlIDwtIHNxcnQocCooMS1wKS9uKQoKIyMgQklOT01JQUwgKE5PUk1BTCBBUFBST1hJTUFUSU9OKQojIFRoZSBsYXJnZXIgdGhlIG51bWJlciBvZiBzdWNjZXNzZXMsIG5wLCBhbmQgZmFpbHVyZXMsIG4oMS1wKSwgdGhlIGJldHRlciB0aGUgbm9ybWFsIGFwcHJveGltYXRpb24gZm9yIGNvbmZpZGVuY2UgaW50ZXJ2YWxzIChwIG5lYXIgMC41LCBuIGFzIGxhcmdlIGFzIHBvc3NpYmxlKQpzYW1wbGUuYmlub20uayA8LSByYmlub20obiA9IG51bV9yZXBlYXRlZF9zYW1wbGVzLCBzaXplID0gbiwgcHJvYiA9IHApCnNhbXBsZS5iaW5vbS5wIDwtIHNhbXBsZS5iaW5vbS5rL24KICAjIyBwb3B1bGF0aW9uIHN0YW5kYXJkIGVycm9yL2NvbmZpZGVuY2UgaW50ZXJ2YWwKICAgIHRydWUuYmlub20ucC5jb25mLjAyLjUgPC0gc2FtcGxlLmJpbm9tLnAtMS45Nip0cnVlLnAuc2UKICAgIHRydWUuYmlub20ucC5jb25mLjk3LjUgPC0gc2FtcGxlLmJpbm9tLnArMS45Nip0cnVlLnAuc2UKICAgIHRydWUuYmlub20udGhldGFfaW5fY29uZiA8LSB0cnVlLmJpbm9tLnAuY29uZi4wMi41IDwgcCAmIHRydWUuYmlub20ucC5jb25mLjk3LjUgPiBwCiAgIyMgc2FtcGxlIHN0YW5kYXJkIGVycm9yL2NvbmZpZGVuY2UgaW50ZXJ2YWwKICAgIHNhbXBsZS5iaW5vbS5wLnNlIDwtIHNxcnQoc2FtcGxlLmJpbm9tLnAqKDEtc2FtcGxlLmJpbm9tLnApL24pCiAgICBzYW1wbGUuYmlub20ucC5jb25mLjAyLjUgPC0gc2FtcGxlLmJpbm9tLnAtMS45NipzYW1wbGUuYmlub20ucC5zZQogICAgc2FtcGxlLmJpbm9tLnAuY29uZi45Ny41IDwtIHNhbXBsZS5iaW5vbS5wKzEuOTYqc2FtcGxlLmJpbm9tLnAuc2UKICAgIHNhbXBsZS5iaW5vbS50aGV0YV9pbl9jb25mIDwtIHNhbXBsZS5iaW5vbS5wLmNvbmYuMDIuNSA8IHAgJiBzYW1wbGUuYmlub20ucC5jb25mLjk3LjUgPiBwCgojIyBCRVRBIERJU1RSSUJVVElPTiAoQ09OVElOVU9VUyBWRVJTSU9OIE9GIEJJTk9NSUFMKQojIFNpbmNlIHRoZSBiaW5vbWlhbCBkaXN0cmlidXRpb24gaXMgbm9uLWNvbnRpbnVvdXMsIHdlIGNhbiBnZXQgY29uZmlkZW5jZSBpbnRlcnZhbHMgY2xvc2VyIHRvIDk1JSBmcm9tIHRoZSBlcXVpdmFsZW50IGJldGEgZGlzdHJpYnV0aW9uIGZvciB0aGUgc2FtZSBucCAmIG4oMS1wKQpzYW1wbGUuYmV0YS5rIDwtIHJiZXRhKG4gPSBudW1fcmVwZWF0ZWRfc2FtcGxlcywgc2hhcGUxID0gcCpuLCBzaGFwZTIgPSAoMS1wKSpuKSpuCnNhbXBsZS5iZXRhLnAgPC0gc2FtcGxlLmJldGEuay9uCiAgIyMgcG9wdWxhdGlvbiBzdGFuZGFyZCBlcnJvci9jb25maWRlbmNlIGludGVydmFsCiAgICB0cnVlLmJldGEucC5jb25mLjAyLjUgPC0gc2FtcGxlLmJldGEucC0xLjk2KnRydWUucC5zZQogICAgdHJ1ZS5iZXRhLnAuY29uZi45Ny41IDwtIHNhbXBsZS5iZXRhLnArMS45Nip0cnVlLnAuc2UKICAgIHRydWUuYmV0YS50aGV0YV9pbl9jb25mIDwtIHRydWUuYmV0YS5wLmNvbmYuMDIuNSA8IHAgJiB0cnVlLmJldGEucC5jb25mLjk3LjUgPiBwCiAgIyMgc2FtcGxlIHN0YW5kYXJkIGVycm9yL2NvbmZpZGVuY2UgaW50ZXJ2YWwKICAgIHNhbXBsZS5iZXRhLnAuc2UgPC0gc3FydChzYW1wbGUuYmV0YS5wKigxLXNhbXBsZS5iZXRhLnApL24pCiAgICBzYW1wbGUuYmV0YS5wLmNvbmYuMDIuNSA8LSBzYW1wbGUuYmV0YS5wLTEuOTYqc2FtcGxlLmJldGEucC5zZQogICAgc2FtcGxlLmJldGEucC5jb25mLjk3LjUgPC0gc2FtcGxlLmJldGEucCsxLjk2KnNhbXBsZS5iZXRhLnAuc2UKICAgIHNhbXBsZS5iZXRhLnRoZXRhX2luX2NvbmYgPC0gc2FtcGxlLmJldGEucC5jb25mLjAyLjUgPCBwICYgc2FtcGxlLmJldGEucC5jb25mLjk3LjUgPiBwCgojIEZpcnN0IG9uZS10aW1lIHNhbXBsZSBjb25maWRlbmNlIGludGVydmFscwpvbmVfdGltZS5zYW1wbGUucC5zZSA8LSBzcXJ0KChrL24pKigxLWsvbikvbikKb25lX3RpbWVfc2FtcGxlLmNvbmZfMDIuNSA8LSAoay9uKS0xLjk2Km9uZV90aW1lLnNhbXBsZS5wLnNlCm9uZV90aW1lX3NhbXBsZS5jb25mXzk3LjUgPC0gKGsvbikrMS45NipvbmVfdGltZS5zYW1wbGUucC5zZQoKIyBPbmUgdGltZSBzYW1wbGUgZWl0aGVyIGNvbnRhaW5zIHRydWUgdmFsdWUgb2YgdGhldGEgb3Igbm90CnBsb3RfbHkodHlwZSA9ICdzY2F0dGVyJywgbW9kZSA9ICdsaW5lcycpICU+JQogIGFkZF90cmFjZSh4ID0gcmVwKGMob25lX3RpbWVfc2FtcGxlLmNvbmZfMDIuNSwgb25lX3RpbWVfc2FtcGxlLmNvbmZfOTcuNSksIGVhY2ggPSAzKSwgeSA9IGMoMSwtMSwwLDAsLTEsMSksIG5hbWUgPSAnQ29uZmlkZW5jZSBpbnRlcnZhbCcpICU+JQogIGFkZF90cmFjZSh4ID0gcCwgeSA9IDAsIG1vZGUgPSAnbWFya2VycycsIG5hbWUgPSAnVHJ1ZSB2YWx1ZScsIG1hcmtlciA9IGxpc3Qoc2l6ZT01MCwgc3ltYm9sID0gJ3gnKSkgJT4lCiAgbGF5b3V0KHNob3dsZWdlbmQgPSBGCiAgICAgICAgICwgeWF4aXMgPSBsaXN0KHJhbmdlID0gYygtMiwgMiksIHplcm9saW5lID0gRiwgc2hvd3RpY2tsYWJlbHMgPSBGKQogICAgICAgICAsIHhheGlzID0gbGlzdChyYW5nZSA9IGMob25lX3RpbWVfc2FtcGxlLmNvbmZfMDIuNSAtIDAuMSwgb25lX3RpbWVfc2FtcGxlLmNvbmZfOTcuNSArIDAuMSkpCiAgICAgICAgICwgdGl0bGUgPSAiT25lLXRpbWUgc2FtcGxlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgZWl0aGVyIGNvbnRhaW5zIHRydWUgdmFsdWUgb2YgdGhldGEgb3Igbm90IikKCiMgQ3VtdWxhdGl2ZSBjb25maWRlbmNlIGludGVydmFscyBjb250YWluIDk1JSBvZiB0aGUgdGltZQpwbG90X2x5KHR5cGUgPSAnc2NhdHRlcicsIG1vZGUgPSAnbGluZXMnKSAlPiUKICBhZGRfdHJhY2UoeCA9IDE6bnVtX3JlcGVhdGVkX3NhbXBsZXMKICAgICAgICAgICAgLCB5ID0gY3Vtc3VtKHRydWUuYmV0YS50aGV0YV9pbl9jb25mKS9jdW1zdW0ocmVwKDEsbnVtX3JlcGVhdGVkX3NhbXBsZXMpKQogICAgICAgICAgICAsIG5hbWUgPSAnQ3VtdWxhdGl2ZSBtZWFuIHdpdGggc2FtcGxpbmcnKSAlPiUKICBsYXlvdXQoc2hvd2xlZ2VuZCA9IEYKICAgICAgICAgIywgeWF4aXMgPSBsaXN0KHJhbmdlID0gYygwLCAxKSkKICAgICAgICAgLCB0aXRsZSA9ICJDdW11bGF0aXZlIGNvbmZpZGVuY2UgaW50ZXJ2YWxzIHRlbmRzIHRvIGNvbnRhaW4gcCA5NSUgb2YgdGhlIHRpbWUiKQoKYGBgCgpJbiBvcmRlciB0byBvYnRhaW4gdGhlc2UgcmVzdWx0cywgY2VydGFpbiBjb25kaXRpb25zIGhhdmUgdG8gYmUgbWV0LCBpbmNsdWRpbmc6CgoqIFRoZSByYW5kb21seSBzYW1wbGVkIG9ic2VydmF0aW9ucyBhcmUgaW5kZXBlbmRlbnQsIHNvIG9ic2VydmluZyBhbnkgb25lIHZhbHVlIGRvZXMgbm90IGhhdmUgYW4gaW1wYWN0IG9uIHdoYXQgc3Vic2VxdWVudCB2YWx1ZXMgd2Ugb2JzZXJ2ZSBtaWdodCBiZS4gSW4gb3VyIGV4YW1wbGUsIGZsaXBwaW5nIGEgaGVhZCBvbmNlIGRvZXMgbm90IGltcGFjdCB0aGUgbGlrZWxpaG9vZCBvZiBmbGlwcGluZyBpdCBhZ2Fpbi4gKihJZiBydW5uaW5nIGFuIGV4cGVyaW1lbnQgaW4gcHJhY3RpY2UsIHRoaXMgbWlnaHQgbWVhbiB0aGF0IG91ciBwb3B1bGF0aW9uIGlzIHN1ZmZpY2llbnRseSBsYXJnZSB3aGVuIGNvbXBhcmVkIHRvIG91ciBzYW1wbGUgdGhhdCB3ZSBkb24ndCBuZWVkIHRvIGJlIGNvbmNlcm5lZCB3aXRoIHJlcGxhY2VtZW50LiBBbm90aGVyIHRoaW5nIHRvIHdhdGNoIG91dCBmb3IgaXMgbmV0d29yayBlZmZlY3RzIC0gaW1hZ2luZSBhbiBhaXJsaW5lIGluY3JlYXNlcyBwcmljZSBvZiBzZWF0cyBhcyB0aGV5IHNlbGwuIFNheSB3ZSB3YW50IHRvIGV4cGVyaW1lbnQgaW4gb2ZmZXJpbmcgc29tZSBjdXN0b21lcnMgYSBzcGVjaWFsIG9mZmVyIGZvciBhaXJsaW5lIHRpY2tldHMsIG91ciB2YXJpYW50LCBhbmQgc29tZSBub3QsIG91ciBjb250cm9sOiB0aGUgY3VzdG9tZXJzIHdpdGggdGhlIHNwZWNpYWwgb2ZmZXIgbWlnaHQgYmUgbW9yZSBsaWtlbHkgdG8gYnV5LCBhbmQgdGhpcyB3aWxsIHNob3J0ZW4gdGhlIHN1cHBseSwgaW5jcmVhc2luZyB0aGUgcHJpY2UgZm9yIHRob3NlIHdpdGhvdXQgdGhlIHNwZWNpYWwgb2ZmZXIsIGFuZCBkZWNyZWFzaW5nIHRoZWlyIGxpa2VsaWhvb2QgdG8gYnV5KS4qCiogQW55IHNhbXBsZWQgb2JzZXJ2YXRpb25zIGFyZSBpZGVudGljYWxseSBkaXN0cmlidXRlZCB0byB0aGUgcG9wdWxhdGlvbiAqKGUuZy4gaWYgd2UgdGFrZSBvdXIgc2FtcGxlIGZyb20gdGhlIFVTQSwgdGhleSBtaWdodCBoYXZlIGEgZGlmZmVyZW50IHByb3BlbnNpdHkgdG8gd2F0Y2ggVFYgdGhhbiB0aGUgVUsuKSoKKiBCZWNhdXNlIGl0IGlzIGEgcmFuZG9tIHNhbXBsZSwgdGhlIHZhbHVlcyBvYnNlcnZlZCBhcmUgY2hhcmFjdGVyaXNlZCBieSBhIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBhc3NvY2lhdGVkIHdpdGggJFx0aGV0YSQuICooZS5nLiB3ZSBkb24ndCBrbm93IHdoYXQgdGhlIG51bWJlciBvZiBoZWFkcyBvYmVydmVkIHdpbGwgYmUgYmVmb3JlIHNhbXBsaW5nLCBidXQgdGhlIGxpa2VsaWhvb2Qgb2Ygd2hhdCB3ZSBvYnNlcnZlIGlzIHByZS1kZXRlcm1pbmVkIHRocm91Z2ggaXRzIGFzc29jaWF0ZWQgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIHdpdGggJFx0aGV0YSQpKgoKIyMgT2theSwgc28gd2hhdCBleGFjdGx5IGRvZXMgYSBCYXllc2lhbiBhcHByb2FjaCBtZWFuPwoKQmF5ZXNpYW4gaW5mZXJlbmNlIGlzIGJyb2FkbHkgc2ltaWxhciB0byBmcmVxdWVudGlzdCBpbmZlcmVuY2UuICoqVGhlIGtleSBkaWZmZXJlbmNlIHRob3VnaCBpcyB0aGF0LCB1bmRlciBhIEJheWVzaWFuIGFwcHJvYWNoLCB0aGUgdHJ1ZSB2YWx1ZSBvZiAkXHRoZXRhJCBpcyB0cmVhdGVkIGFzIGEgcmFuZG9tIHZhcmlhYmxlLCByYXRoZXIgdGhhbiBhIGZpeGVkIGNvbnN0YW50LioqIAoKU28sIGZvciBleGFtcGxlLCB3ZSBtaWdodCBiZWxpZXZlIHRoYXQgaW4gb3VyIGVjb25vbXksICQ5MCQlIG9mIGNvaW5zIGFyZSBmYWlyLCBhbmQgJDEwJCUgb2YgY29pbnMgYXJlIGJpYXNlZCwgd2l0aCBiaWFzZWQgY29pbnMgZmxpcHBpbmcgaGVhZHMgJGByIGsqMTBgJCUgb2YgdGhlIHRpbWUuIAoKVW5kZXIgdGhlIGd1aXNlIG9mIGJlaW5nIGZyZXF1ZW50aXN0cyBwcmV2aW91c2x5LCB3ZSBoYWQgbm8gcHJpb3IgYmVsaWVmIGFzIHRvIHdoYXQgJFx0aGV0YSQgd291bGQgYmU6IHdlIG9ubHkgbWFkZSBhbiBlZHVjYXRlZCBndWVzcyBiYXNlZCBvbiB0aGUgYHIga2AgaGVhZHMgd2Ugb2JzZXJ2ZWQuIFdlIGJlbGlldmVkIHRoYXQgdGhlcmUgaXMgb25lIGZpeGVkIHZhbHVlIG9mIHRoZSB0cnVlICRcdGhldGEkLCBhbmQgdGhhdCB0aGVyZSB3YXMgb25seSByYW5kb21uZXNzIGFzc29jaWF0ZWQgd2l0aCBzYW1wbGluZywgc28gd2UgY3JlYXRlZCBhIGNvbmZpZGVuY2UgaW50ZXJ2YWwgdG8gcG9ydHJheSB0aGlzLgoKTm93LCBhcyBiYXllc2lhbnMsIHdlIGFyZSBhbHNvIGluY29ycG9yYXRpbmcgb3VyIHByaW9yIGJlbGllZnMgYXMgdG8gd2hhdCAkXHRoZXRhJCBpcyAtIHRoYXQgaXQgaXMgZWl0aGVyIGZhaXIgb3IgYmlhc2VkLiBXZSBiZWxpZXZlIHRoYXQgdGhlcmUgaXMgbm90IGp1c3QgcmFuZG9tIGVycm9yIGFzc29jaWF0ZWQgaW4gc2FtcGxpbmcgLSB3ZSBhbHNvIHRyZWF0ICRcdGhldGEkIGFzIGFuIGFkZGl0aW9uYWwgcmFuZG9tIHZhcmlhYmxlLCBzaW5jZSB3ZSBkb24ndCBrbm93IHdoZXRoZXIgb3VyIGNvaW4gaXMgZmFpciBvciBiaWFzZWQgZWl0aGVyLCBhbmQgZmFpciBjb2lucyB3aWxsIGhhdmUgYSBkaWZmZXJlbnQgc2FtcGxlIG1lYW4gZGlzdHJpYnV0aW9uIHRoYW4gYmlhc2VkIG9uZXMuCgpgYGAge3IsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD03fQpmYWlyX2NvaW5fa19wcm9iIDwtIGJpbm9taWFsX3Byb2JhYmlsaXR5KGssIG4sIHApCmJpYXNlZF9jb2luX2tfcHJvYiA8LSBiaW5vbWlhbF9wcm9iYWJpbGl0eShrLCBuLCBrL24pCmBgYAoKR2l2ZW4gdGhhdCB3ZSBvYnNlcnZlIGByIGtgIGhlYWRzLCB0aGUgbGlrZWxpaG9vZCBvZiB0aGlzIG9jY3VyaW5nIGlmIHRoZSBjb2luIGlzIGZhaXIgaXMgJGByIHBlcmNlbnQoZmFpcl9jb2luX2tfcHJvYilgJCUsIGFuZCAkYHIgcGVyY2VudChiaWFzZWRfY29pbl9rX3Byb2IpYCQlIGlmIHRoZSBjb2luIGlzIGJpYXNlZC4gSW4gdGhlIGFic2VuY2Ugb2YgaW5mb3JtYXRpdmUgcHJpb3IgaW5mb3JtYXRpb24gdGhlbiwgaXQgbWlnaHQgYXBwZWFyIHRoYXQgdGhlIGNvaW4gaXMgbW9yZSBsaWtlbHkgdG8gYmUgYmlhc2VkLgoKSG93ZXZlciwgd2UgYWxzbyBuZWVkIHRvIHRha2UgaW50byBhY2NvdW50IHRoYXQgJDkwJCUgb2YgY29pbnMgaW4gdGhlIHBvcHVsYXRpb24gYXJlIGZhaXIsIHNvIGV2ZW4gYmVmb3JlIG9ic2VydmluZyBgciBrYCBoZWFkcywgd2UgaGF2ZSBzb21lIGJlbGllZiBhYm91dCB3aGV0aGVyIHRoZSBjb2luIGlzIGZhaXIgb3IgYmlhc2VkIChpLmUuIHRoZSBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb24gYXNzb2NpYXRlZCB3aXRoIHRoZSByYW5kb20gdmFyaWFibGUgJFx0aGV0YSQpLiAKCmBgYCB7ciwgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTd9CmZhaXJfY29pbl9wcm9iIDwtIChmYWlyX2NvaW5fa19wcm9iICogMC45KS8oKGZhaXJfY29pbl9rX3Byb2IgKiAwLjkpICsgKGJpYXNlZF9jb2luX2tfcHJvYiAqIDAuMSkpCmJpYXNlZF9jb2luX3Byb2IgPC0gKGJpYXNlZF9jb2luX2tfcHJvYiAqIDAuMSkvKChmYWlyX2NvaW5fa19wcm9iICogMC45KSArIChiaWFzZWRfY29pbl9rX3Byb2IgKiAwLjEpKQoKIyBkYXRhLmZyYW1lKAojIG1hdHJpeChkYXRhID0gYyhiaW5vbWlhbF9wcm9iYWJpbGl0eSgyLDEwLDAuNSkqMC45ICMgcChmYWlyLCAyIGhlYWRzKQojICAgICAgICAgICAgICAgICAsICgxLWJpbm9taWFsX3Byb2JhYmlsaXR5KDIsMTAsMC41KSkqMC45ICMgcChmYWlyLCBub3QgMiBoZWFkcykKIyAgICAgICAgICAgICAgICAgLCAwLjkgIyBwKGZhaXIpCiMgICAgICAgICAgICAgICAgICwgYmlub21pYWxfcHJvYmFiaWxpdHkoMiwxMCwwLjIpKjAuMSAjIGJpYXNlZCwgMiBoZWFkcwojICAgICAgICAgICAgICAgICAsICgxLWJpbm9taWFsX3Byb2JhYmlsaXR5KDIsMTAsMC4yKSkqMC4xICMgYmlhc2VkLCBub3QgMiBoZWFkcwojICAgICAgICAgICAgICAgICAsIDAuMQojICAgICAgICAgICAgICAgICAsIGJpbm9taWFsX3Byb2JhYmlsaXR5KDIsMTAsMC41KSowLjkgKyBiaW5vbWlhbF9wcm9iYWJpbGl0eSgyLDEwLDAuMikqMC4xCiMgICAgICAgICAgICAgICAgICwgKDEtYmlub21pYWxfcHJvYmFiaWxpdHkoMiwxMCwwLjUpKSowLjkgKyAoMS1iaW5vbWlhbF9wcm9iYWJpbGl0eSgyLDEwLDAuMikpKjAuMQojICAgICAgICAgICAgICAgICAsIDEKIyAgICAgICAgICAgICAgICAgKQojICAgICAgICAsIG5yb3cgPSAzCiMgICAgICAgICwgZGltbmFtZXMgPSBsaXN0KGMoJ0ZsaXAgMiBoZWFkcycsICdOb3QgZmxpcCAyIGhlYWRzJywgJ1RvdGFsJykKIyAgICAgICAgICAgICAgICAgICAgICAgICAgLCBjKCdGYWlyJywgJ0JpYXNlZCcsICdUb3RhbCcpKQojICAgICAgICApCiMgKQpgYGAKCi4uYW5kIHNvIHdlIGNhbiBmaW5kIHRoZSBsaWtlbGlob29kIHdlIGdvdCBhIGZhaXIgY29pbiwgZ2l2ZW4gdGhlIGZhY3Qgd2Ugb2JzZXJ2ZWQgMiBoZWFkczoKCiQkClAoXHRleHR7ZmFpcn18SD1gciBrYCkgCj1cZnJhY3tQKFx0ZXh0e0g9YHIga2AgYW5kIGZhaXJ9KX17UChcdGV4dHtIPWByIGtgIGFuZCBmYWlyfSkrUChcdGV4dHtIPWByIGtgIGFuZCBiaWFzZWR9KX0KPVxmcmFje1AoXHRleHR7SD1gciBrYHxmYWlyfSkgXHRpbWVzIFAoXHRleHR7ZmFpcn0pfXtQKFx0ZXh0e0g9YHIga2B9KX0KJCQKCiQkClAoXHRleHR7ZmFpcn18SD1gciBrYCkKPVxmcmFje2ByIHJvdW5kKGZhaXJfY29pbl9rX3Byb2IsNClgIFx0aW1lcyAwLjl9e2ByIHJvdW5kKGZhaXJfY29pbl9rX3Byb2IsNClgICsgYHIgcm91bmQoYmlhc2VkX2NvaW5fa19wcm9iLDQpYH09YHIgcm91bmQoZmFpcl9jb2luX3Byb2IsIDQpYAokJAoKJCQKUChcdGV4dHtiaWFzZWR9fEg9YHIga2ApIAo9XGZyYWN7UChcdGV4dHtIPWByIGtgIGFuZCBiaWFzZWR9KX17UChcdGV4dHtIPWByIGtgIGFuZCBmYWlyfSkrUChcdGV4dHtIPWByIGtgIGFuZCBiaWFzZWR9KX0KPVxmcmFje1AoXHRleHR7SD1gciBrYHxiaWFzZWR9KSBcdGltZXMgIFAoXHRleHR7Ymlhc2VkfSl9e1AoXHRleHR7SD1gciBrYH0pfQokJAokJApQKFx0ZXh0e2JpYXNlZH18SD1gciBrYCkgCj1cZnJhY3tgciByb3VuZChiaWFzZWRfY29pbl9rX3Byb2IsNClgIFx0aW1lcyAwLjF9e2ByIHJvdW5kKGZhaXJfY29pbl9rX3Byb2IsNClgICsgYHIgcm91bmQoYmlhc2VkX2NvaW5fa19wcm9iLDQpYH09YHIgcm91bmQoYmlhc2VkX2NvaW5fcHJvYiwgNClgCiQkCgpJbiBvdGhlciB3b3Jkcywgb3VyIHByaW9yIGJlbGllZiAoYmVmb3JlIHNhbXBsaW5nIGFuZCBvYnNlcnZpbmcgYW55IGRhdGEpIHdhcyB0aGF0IHRoZSBsaWtlbGlob29kIG9mIG91ciBjb2luIGhhdmluZyAkXHRoZXRhJCBlcXVhbCB0byAkYHIgcGAkIHdhcyAkOTBcJSQsIGFuZCB0aGUgbGlrZWxpaG9vZCBvZiBpdCBoYXZpbmcgdGhldGEgZXF1YWwgdG8gJGByIGsvbmAkIHdhcyAkMTBcJSQuIEFmdGVyIG9ic2VydmluZyBgciBrYCBoZWFkcywgd2UgdXBkYXRlIG91ciBiZWxpZWZzLCBzbyB0aGF0IHRoZSBsaWtlbGlob29kIG9mIHRoZSBwcm9iYWJpbGl0eSBvZiBvdXIgY29pbiBmbGlwcGluZyBoZWFkcyAoJFx0aGV0YSQpIGJlaW5nIGVxdWFsIHRvICQwLjUkIGlzIG5vdyBlcXVhbCB0byAkYHIgcm91bmQoZmFpcl9jb2luX3Byb2IqMTAwLDIpYFwlJCwgYW5kIG9mIGl0IGJlaW5nIGVxdWFsIHRvICRgciBzYW1wbGVfbWVhbmAkIGJlaW5nICRgciByb3VuZChiaWFzZWRfY29pbl9wcm9iKjEwMCwyKWBcJSQKCkl0IGlzIHRoaXMgaW5jb3Jwb3JhdGlvbiBvZiBwcmlvciBkYXRhIHRoYXQgaXMgZWl0aGVyIHNlZW4gYXMgQmF5ZXNpYW4ncyBiaWdnZXN0IGFkdmFudGFnZSBvciBwaXRmYWxsLiBPbiB0aGUgb25lIGhhbmQsIGV4cGVyaW1lbnRzIGFyZSBub3QgYWJzdHJhY3QgZGV2aWNlcywgYW5kIHNvbWUga25vd2xlZGdlIGFib3V0IHRoZSBwcm9jZXNzIGJlaW5nIGludmVzdGlnYXRlZCBiZWZvcmUgb2J0YWluaW5nIHRoZSBkYXRhIGlzIGtub3duIGFuZCBhcmd1YWJseSBzaG91bGQgYmUgaW5jb3Jwb3JhdGVkLiBPbiB0aGUgb3RoZXIsIGluY29ycG9yYXRpbmcgc3ViamVjdGl2ZSBvcGluaW9ucywgcGFydGljdWxhcmx5IHN0cm9uZyBvbmVzLCBtYXkgbWVhbiB0aGF0IHlvdSBkbyBub3QgbGVhcm4gdGhlIHRydWUgdmFsdWVzIHlvdSBhcmUgdHJ5aW5nIHRvIGRlcml2ZS4gQmF5ZXNpYW4gaXMgdGh1cyBhbmFseXNpcyB0aGF0IHVzZXMgYSBzZXQgb2Ygb2JzZXJ2YXRpb25zIHRvIGNoYW5nZSBvcGluaW9uIHJhdGhlciB0aGFuIGFzIGEgbWVhbnMgdG8gZGV0ZXJtaW5lIHVsdGltYXRlIHRydXRoLgoKVG8gaGVscCBkZXNjcmliZSBiYXllc2lhbiBhbmFseXNpcywgdGhlIGZvbGxvd2luZyB0ZXJtcyBhcmUgb2Z0ZW4gdXNlZDoKCiogUHJpb3IgZGlzdHJpYnV0aW9uOiAkUHIoXHRoZXRhKSQgLSByZXByZXNlbnRzIGV4aXN0aW5nIGJlbGllZiBhYm91dCAkXHRoZXRhJCAoKlJlcHJlc2VudHMgd2hhdCB3YXMgdGhvdWdodCBiZWZvcmUgc2VlaW5nIHRoZSBkYXRhKikuIEZvciBleGFtcGxlLCBpbiB0aGUgYmlub21pYWwgY29pbiBleGFtcGxlIGFib3ZlLCB3ZSBoYXZlIHByaW9yIGtub3dsZWRnZSB0aGF0IDkwJSBvZiBjb2lucyBpbiBvdXIgZWNvbm9teSBhcmUgZmFpciwgc28gJFAoXHRoZXRhKT1QKEJpYXNlZCk9MC4xJAoqIEV2aWRlbmNlOiAkWCQgLSB3aGF0IHdlIGp1c3Qgb2JzZXJ2ZWQgKCRgciBrYCQgaGVhZHMpCiogTWFyZ2luYWwgcHJvYmFiaWxpdHk6ICRQcihYKSQgLSB0aGUgdG90YWwgcHJvYmFiaWxpdHkgb2YgdGhlIGRhdGEgYWNyb3NzIGFsbCBwb3NzaWJsZSB2YWx1ZXMgb2YgdGhlIHBhcmFtZXRlciAkXHRoZXRhJC4gSXQgZG9lc24ndCBhY3R1YWxseSBkZXBlbmQgb24gJFx0aGV0YSQgYW5kIGlzb2Z0ZW4gcmVmZXJyZWQgdG8gYXMgdGhlIHByb3BvcnRpb25hbGl0eSBmYWN0b3Ivbm9ybWFsaXNpbmcgY29uc3RhbnQgKGl0IG1ha2VzIHN1cmUgYWxsIHRoZSBzY2VuYXJpb3MgYXJlIG1vZGVsbGVkLiBGb3IgZXhhbXBsZSwgJFAoSD1gciBrYCkgPSBQKEg9YHIga2B8RmFpcikgXHRpbWVzIFAoRmFpcikgKyBQKEg9YHIga2B8Qmlhc2VkKSBcdGltZXMgUChCaWFzZWQpJCkKKiBMaWtlbGlob29kIGZ1bmN0aW9uOiAkUHIoWHxcdGhldGEpJCAtIHRoZSBwcm9iYWJpbGl0eSBvZiAkXHRoZXRhJCBnaXZlbiB0aGUgZGF0YSAgb2JzZXJ2ZWQgKCpSZXByZXNlbnRzIHRoZSBuZXcgZGF0YSBhdmFpbGFibGUqKS4gRm9yIGV4YW1wbGUsICRQKEg9YHIga2B8Qmlhc2VkKT1gciBiaWFzZWRfY29pbl9rX3Byb2JgJAoqIEpvaW50IHByb2JhYmlsaXR5IGRlbnNpdHkgZnVuY3Rpb246ICRQcihYLFx0aGV0YSk9UHIoKFh8XHRoZXRhKS5QcihcdGhldGEpJCAtIHVzZWQgdG8gbW9kaWZ5IHByaW9yIGJlbGllZnMgdGhyb3VnaCBCYXllcyBUaGVvcmVtCiogUG9zdGVyaW9yIGRpc3RyaWJ1dGlvbjogJFByKFx0aGV0YXxYKSQgLSB0aGUgKnBvc3RlcmlvciBkZW5zaXR5KiByZXByZXNlbnRzIHRoZSBrbm93bGVkZ2UgYWJvdXQgdGhlIG1vZGVsIHBhcmFtZXRlcnMgYWZ0ZXIgb2JzZXJ2aW5nIHRoZSBkYXRhICgqUmVwcmVzZW50cyB3aGF0IGlzIG5vdyB0aG91Z2h0IGdpdmVuIGJvdGggcHJpb3IgZGF0YSBhbmQgZGF0YSBqdXN0IG9idGFpbmVkKikKKiBDb25qdWdhbmN5OiBvY2N1cnMgd2hlbiB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBpcyBpbiB0aGUgc2FtZSBmYW1pbHkgb2YgcHJvYmFiaWxpdHkgZGVuc2l0eSBmdW5jdGlvbnMgYXMgdGhlIHByaW9yIGJlbGllZiwgYnV0IHdpdGggbmV3IHBhcmFtZXRlciB2YWx1ZXMgKHVwZGF0ZWQgdG8gcmVmbGVjdCB3aGF0IGhhcyBiZWVuIGxlYXJuZWQgZnJvbSB0aGUgZGF0YSkuIFRoZSBwb3N0ZXJpb3IgY29tZXMgZnJvbSB0aGUgc2FtZSBmYW1pbHkgYXMgdGhlIHByaW9yLCByYXRoZXIgdGhhbiB0aGUgZGF0YSdzIGRpc3RyaWJ1dGlvbi4KCkFuZCB0aHVzLCB3ZSBjYW4gdGhlbiBkZXNjcmliZSBCYXllcyBUaGVvcmVtOgoKJCQKUChcdGhldGF8WCkgPVxmcmFje1AoWHxcdGhldGEpIFx0aW1lcyBQKFx0aGV0YSl9e1AoWHxcdGhldGEpIFx0aW1lcyBQKFx0aGV0YSkgKyBQKFh8XHRoZXRhJykgXHRpbWVzIFAoXHRoZXRhJyl9ID1cZnJhY3tQKFh8XHRoZXRhKSBcdGltZXMgUChcdGhldGEpfXtQKFgpfQokJAoKT2theSAtIHRoZSBleGFtcGxlIGFib3ZlIG1pZ2h0IG5vdCBxdWl0ZSBiZSBhIGZhaXIgY29tcGFyaXNvbiwgc2luY2UgdGhlIEJheWVzaWFuIGV4YW1wbGUgaGFkIHF1aXRlIGEgc3Ryb25nIHByaW9yOiB0aGF0IHRoZXJlIHdlcmUgb25seSB0d28gcG9zc2libGUgdmFsdWVzIGZvciB0aGV0YSwgYW5kIHRoYXQgOTAlIG9mIHRoZSB0aW1lIGl0IGlzIDAuNS4KCkEgbW9yZSAnb2JqZWN0aXZlJyBwcmlvciB0aGF0IGlzIGEgZmFpcmVyIGNvbXBhcmlzb24gdG8gdGhlIGZyZXF1ZW50aXN0IGV4YW1wbGUgaXMgdG8gZ2l2ZSBhbGwgdmFsdWVzIG9mIHRoZXRhIGhhdmUgYW4gZXF1YWwgbGlrZWxpaG9vZCAtIGluIG90aGVyIHdvcmRzLCBhIHVuaWZvcm0gZGlzdHJpYnV0aW9uLiBXZSBjYW4gbW9kZWwgdGhpcyB1c2luZyBhIGJldGEgZGlzdHJpYnV0aW9uLiBHb2luZyBmb3J3YXJkcyB0b28sIGxldCdzIG1ha2UgdGhpcyBtb3JlIGdlbmVyaWMsIGFuZCB0ZXJtIHRoZSBudW1iZXIgb2YgaGVhZHMgb2JzZXJ2ZWQgaW4gdGhlIHNhbXBsZSBhcyAkayQuCgoqQSBxdWljayBpbnRyb2R1Y3Rpb24gdG8gdGhlIGJldGEgZGlzdHJpYnV0aW9uOiBpdCBjYW4gbW9kZWwgbG90cyBvZiBkaWZmZXJlbnQgZnVuY3Rpb25hbCBmb3JtcyB1c2luZyAkYSQgYW5kICRiJCBhcyBwYXJhbWV0ZXJzLCBieSBpbnB1dHRpbmcgdGhlbSBpbnRvIHRoZSBmb2xsb3dpbmcgZnVuY3Rpb246KgoKJCQKXHRleHR7QmV0YX1bYSxiXSBcc2ltIFx0aGV0YV57YS0xfVx0aW1lcygxLVx0aGV0YSlee2ItMX0KJCQKClNvIC0gaWYgd2Ugd2FudCB0byBjcmVhdGUgYSB1bmlmb3JtIGRpc3RyaWJ1dGlvbiBmb3Igb3VyIHByaW9yLCB3ZSBjYW4gbW9kZWwgdGhpcyB1c2luZyBhIGJldGEgZGlzdHJpYnV0aW9uIGJ5IHNldHRpbmcgJGEkIGFuZCAkYiQgdG8gYm90aCBlcXVhbCB0byAxCgokJApwKFx0aGV0YSkgXHNpbSBcdGV4dHtCZXRhfVsxLDFdIFxzaW0gXHRoZXRhXnsxLTF9XHRpbWVzKDEtXHRoZXRhKV57MS0xfT1cdGhldGFeezB9XHRpbWVzKDEtXHRoZXRhKV57MH09IDEgXHRleHR7IChmb3IgYWxsIHZhbHVlcyBvZiB9XHRoZXRhKQokJAoKQW5kIHdlIGNhbiBtb2RlbCBvdXIgbGlrZWxpaG9vZCB1c2luZyB0aGUgYmlub21pYWwgZnVuY3Rpb24KCiQkCnAoWHwgXHRoZXRhKSA9IHAoXHRleHR7SD19a3wgXHRoZXRhKSA9IFx0ZXh0e0Jpbm9tfShuLHApIFxzaW0gXHRoZXRhXmtcdGltZXMoMS1cdGhldGEpXntuLWt9CiQkCgpBbmQgZmluYWxseSAtIHRoZSBwb3N0ZXJpb3IgaXMgcHJvcG9ydGlvbmFsIHRvIHRoZSBwcmlvciBtdWx0aXBsaWVkIGJ5IHRoZSBsaWtlbGlob29kOgoKJCQKcChcdGhldGEpIFx0aW1lcyBwKFh8IFx0aGV0YSkgXHNpbSBbXHRoZXRhXnthLTF9XHRpbWVzKDEtXHRoZXRhKV57Yi0xfV0gXHRpbWVzIFtcdGhldGFea1x0aW1lcygxLVx0aGV0YSlee24ta31dID0gXHRoZXRhXnthLTEra31cdGltZXMoMS1cdGhldGEpXntiLTErbi1rfQokJAoKV2hpY2ggd2UgY2FuIHB1cmVseSBwYXJhbWV0aXplIGluIGEgYmV0YSBkaXN0cmlidXRpb24gKHlvdSBjYW4gc2VlIHRoYXQsIHRoZSBzdHJvbmdlciB0aGUgcHJpb3IgLSBhbmQgaGVuY2UgdGhlIGxhcmdlciBhIGFuZCBiIC0gdGhlIHNtYWxsZXIgdGhlIGltcGFjdCBuZXcgZXZpZGVuY2UgayBhbmQgbiBoYXMgb24gdGhlIHBvc3RlcmlvciBkaXN0cmlidXRpb24pOgoKJCQKXHRoZXRhXnthLTEra31cdGltZXMoMS1cdGhldGEpXntiLTErbi1rfSBcc2ltIFx0ZXh0e0JldGF9W2ErayxiK24ta10gCiQkCgooTm90ZSB0aGlzIGlzIGFuIGFwcHJveGltYXRpb24gLSB0aGUgYWN0dWFsIGVxdWFsaXR5IGlzIHNwZWNpZmllZCBsYXRlciwgYXMgYW4gZXhhbXBsZSBvZiBjb25qdWdhbmN5KQoKYGBgIHtyLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9N30KCmdhbW1hX2Z1bmN0aW9uIDwtIGZ1bmN0aW9uKG4pIHsKICByZXR1cm4oZmFjdG9yaWFsKG4tMSkpCn0KCmJldGFfcHJvYmFiaWxpdHkgPC0gZnVuY3Rpb24odGhldGEsYSxiKSB7CiAgbnVtZXJhdG9yIDwtICgodGhldGEpXihhLTEpKSooKDEtdGhldGEpXihiLTEpKQogIGRlbm9taW5hdG9yIDwtIChnYW1tYV9mdW5jdGlvbihhKSpnYW1tYV9mdW5jdGlvbihiKSkvZ2FtbWFfZnVuY3Rpb24oYStiKQogIHJldHVybihudW1lcmF0b3IvZGVub21pbmF0b3IpCn0KCmEgPC0gMQpiIDwtIDEKCiMgdW5pZm9ybSBkaXN0cmlidXRpb24KIyBwcmlvciA8LSBkYmV0YSh4ID0geCwgc2hhcGUxID0gMSwgc2hhcGUyID0gMSkKeCA8LSBzZXEoMCwgMSwgbGVuZ3RoPTEwMCsxKQpwcmlvciA8LSBzYXBwbHkoeCwgRlVOID0gZnVuY3Rpb24odGhldGEpIHtiZXRhX3Byb2JhYmlsaXR5KHRoZXRhLGEsYil9KQoKIyBiaW5vbWlhbCBkaXN0cmlidXRpb24KbGlrZWxpaG9vZF9mLmJpbm9tIDwtIHNhcHBseSh4LCBGVU4gPSBmdW5jdGlvbih0aGV0YSkge2Jpbm9taWFsX3Byb2JhYmlsaXR5KGssbix0aGV0YSl9KQpsaWtlbGlob29kX2YuYmlub20uaW50IDwtIGxpa2VsaWhvb2RfZi5iaW5vbQpsaWtlbGlob29kX2YuYmlub20uaW50W3JvdW5kKHgqbiwwKSAhPSB4Km5dIDwtIE5BCgojIGJldGEgZGlzdHJpYnV0aW9uCmxpa2VsaWhvb2RfZi5iZXRhIDwtIHNhcHBseSh4LCBGVU4gPSBmdW5jdGlvbih0aGV0YSkge2JldGFfcHJvYmFiaWxpdHkodGhldGEsaysxLG4taysxKSoxLyhuKzEpfSkKCnBvc3RlcmlvciA8LSBzYXBwbHkoeCwgRlVOID0gZnVuY3Rpb24odGhldGEpIHtiZXRhX3Byb2JhYmlsaXR5KHRoZXRhLGEraysxLGIrbi1rKzEpKjEvKG4rMSl9KQoKcGxvdF9seSh0eXBlID0gJ3NjYXR0ZXInLCBtb2RlID0gJ2xpbmVzJykgJT4lCiAgYWRkX3RyYWNlKHggPSB4LCB5ID0gcHJpb3Ivc3VtKHByaW9yKSwgbmFtZSA9ICdQcmlvcjogVW5pZm9ybSA9IEJldGEoMSwxKScpICU+JQogIGFkZF90cmFjZSh4ID0geCwgeSA9IGxpa2VsaWhvb2RfZi5iaW5vbS5pbnQsIG5hbWUgPSAnTGlrZWxpaG9vZDogfiBCaW5vbShrPTIscD10aGV0YSxuKScsIG1vZGUgPSAnbWFya2VycycpICU+JQogIGFkZF90cmFjZSh4ID0geCwgeSA9IGxpa2VsaWhvb2RfZi5iZXRhLCBuYW1lID0gJ0xpa2VsaWhvb2Q6IH4gQmV0YShwPXRoZXRhLGssbi1rKScpICU+JQogIGFkZF90cmFjZSh4ID0geCwgeSA9IHBvc3RlcmlvciwgbmFtZSA9ICdQb3N0ZXJpb3I6IH4gQmV0YShhK2ssYituLWspJykgJT4lCiAgbGF5b3V0KHhheGlzID0gbGlzdCh0aXRsZSA9ICdUaGV0YScpKQpgYGAKCkFzIHlvdSBjYW4gc2VlLCB3aXRoIGEgdmVyeSAnb2JqZWN0aXZlJyBwcmlvciwgdGhlIEJheWVzaWFuIHBvc3RlcmlvciBpcyB2ZXJ5IHNpbWlsYXIgdG8gdGhlIHJlc3VsdCBkZXJpdmVkIGZyb20gdGhlIGZyZXF1ZW50aXN0IGV2aWRlbmNlLW9ubHkgZGlzdHJpYnV0aW9uICh0aGUgQmF5ZXNpYW4gbGlrZWxpaG9vZCBmdW5jdGlvbikuCgpOb3RlIGhlcmUgdGhhdCB0aGlzIGEgZ29vZCBleGFtcGxlIG9mIGNvbmp1Z2FuY3kgLSBzZWUgdGhlIHNlY3Rpb24gYmVsb3cgb24gd2hhdCB0aGF0IG1lYW5zIGV4YWN0bHkuCgpJbiB0aGUgdHdvIEJheWVzaWFuIGV4YW1wbGVzIGFib3ZlIHRob3VnaCwgd2UgZWl0aGVyIGhhZCBhIHZlcnkgd2VhayBwcmlvciAodGhlIHVuaWZvcm0gZGlzdHJpYnV0aW9uKSBvciBhIHZlcnkgc3Ryb25nIHByaW9yIChvbmx5IHR3byBhdmFpbGFibGUgdmFsdWVzIGZvciB0aGV0YSwgYW5kIDkwJSBsaWtlbGlob29kIHRoZSBjb2luIGlzIGZhaXIpLiBCYXllc2lhbiB0ZW5kcyB0byBtb3N0IHZhbHVhYmxlIHdoZXJlIGJvdGggdGhlIG5ldyBkYXRhIGFuZCBwYXN0IHByaW9yIGhhdmUgbW9yZSBlcXVhbCBpbmZsdWVuY2UsIGFuZCB0aGUgcG9zdGVyaW9yIGZvcm1pbmcgYSBkaXN0cmlidXRpb24gdGhhdCBzaXRzIHNvbWV3aGVyZSBiZXR3ZWVuIHRoYXQgZXN0aW1hdGVkIGJ5IHRoZSBwcmlvciBhbmQgbGlrZWxpaG9vZCBmdW5jdGlvbjogCgpTbyAtIGxldCdzIHNheSB0aGUgbGFzdCBjb2luIHdlIHRyaWVkIGZsaXBwaW5nIGByIG5gIHRpbWVzIGdvdCBoZWFkcyBgciBwKm5gIHRpbWVzIChvdXIgcHJpb3IpIGFuZCB0aGUgbmV3IGNvaW4gZmxpcHBlZCBoZWFkcyBgciBrYCB0aW1lcyAob3VyIG5ldyBldmlkZW5jZSkuIFdlIGNhbiB0aGVuIGdldCB0aGUgZm9sbG93aW5nIGVxdWF0aW9uczoKCmBgYCB7ciwgZWNobz1GQUxTRX0KazEgPC0gNQpuMSA8LSAxMAprMiA8LSBrCm4yIDwtIDEwCmBgYAoKJCQKXHRleHR7UHJpb3I6IH0gXHRleHR7QmV0YX1ba197MX0sbl97MX0ta197MX1dID0gXHRleHR7QmV0YX1bYHIgazFgLGByIG4xYC1gciBrMWBdID0gXHRleHR7QmV0YX1bYHIgazFgLGByIG4xLWsxYF0KJCQKJCQKXHRleHR7TGlrZWxpaG9vZDogfSBcdGV4dHtCZXRhfVtrX3syfSxuX3syfS1rX3syfV0gPSBcdGV4dHtCZXRhfVtgciBrMmAsYHIgbjJgLWByIGsyYF0gPSBcdGV4dHtCZXRhfVtgciBrMmAsYHIgbjItazJgXQokJAoKJCQKXHRleHR7UG9zdGVyaW9yOiB9IFx0ZXh0e0JldGF9W2tfezF9K2tfezJ9LG5fezF9LWtfezF9K25fezJ9LWtfezJ9XSA9IFx0ZXh0e0JldGF9W2ByIGsxYCArIGByIGsyYCxgciBuMS1rMWAgKyBgciBuMi1rMmBdID0gXHRleHR7QmV0YX1bYHIgazErazJgLGByIG4xLWsxK24yLWsyYF0KJCQKYGBgIHtyLCBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9N30KIyBwcmlvciA8LSBzYXBwbHkoeCwgRlVOID0gZnVuY3Rpb24odGhldGEpIHtiZXRhX3Byb2JhYmlsaXR5KHRoZXRhLGsxKzEsbjEtazErMSkvKG4xKzEpfSkKIyBsaWtlbGlob29kX2YgPC0gc2FwcGx5KHgsIEZVTiA9IGZ1bmN0aW9uKHRoZXRhKSB7YmV0YV9wcm9iYWJpbGl0eSh0aGV0YSxrMisxLG4yLWsyKzEpLyhuMisxKX0pCiMgcG9zdGVyaW9yIDwtIHNhcHBseSh4LCBGVU4gPSBmdW5jdGlvbih0aGV0YSkge2JldGFfcHJvYmFiaWxpdHkodGhldGEsazErazIrMixuMS1rMSsxK24yLWsyKzEpLyhuMStuMisyKX0pCgojIHByaW9yIDwtIGRiZXRhKHgsIGsxKzEsIG4xLWsxKzEpLyhuMSsxKQojIGxpa2VsaWhvb2RfZiA8LSBkYmV0YSh4LCBrMisxLCBuMi1rMisxKS8objIrMSkKIyBwb3N0ZXJpb3IgPC0gZGJldGEoeCwgazErazIrMSwgbjEtazErbjItazIrMSkvKG4xK24yKzEpCgpwcmlvciA8LSBkYmV0YSh4LCBrMSwgbjEtazEpCmxpa2VsaWhvb2RfZiA8LSBkYmV0YSh4LCBrMiwgbjItazIpCnBvc3RlcmlvciA8LSBkYmV0YSh4LCBrMStrMiwgbjEtazErbjItazIpCgpwbG90X2x5KHR5cGUgPSAnc2NhdHRlcicsIG1vZGUgPSAnbGluZXMnKSAlPiUKICBhZGRfdHJhY2UoeCA9IHgsIHkgPSBwcmlvciwgbmFtZSA9ICdQcmlvciBiZWxpZWY6IEhvcnNlJykgJT4lCiAgYWRkX3RyYWNlKHggPSB4LCB5ID0gbGlrZWxpaG9vZF9mLCBuYW1lID0gJ0xpa2VsaWhvb2QgKE5ldyBkYXRhKTogRG9ua2V5JykgJT4lCiAgYWRkX3RyYWNlKHggPSB4LCB5ID0gcG9zdGVyaW9yLCBuYW1lID0gJ1Bvc3RlcmlvciBCZWxpZWY6IE11bGUnKSAlPiUKICBsYXlvdXQodGl0bGUgPSAiVXBkYXRpbmcgUHJpb3IgQmVsaWVmcyIpCmBgYAoKVGhlIHBvc3RlcmlvciBjdXJ2ZSBpcyBib3RoIHRhbGxlciBhbmQgbmFycm93IHRoYW4gYm90aCB0aGUgZGlzdHJpYnV0aW9ucyBlc3RpbWF0ZWQgZnJvbSB0aGUgcHJpb3IgYW5kIHRoZSBsaWtlbGlob29kIGZ1bmN0aW9ucy4gVGhpcyBpcyBiZWNhdXNlLCBieSBpbmNsdWRpbmcgYm90aCBwcmlvciBkYXRhIGFuZCBuZXcgZXZpZGVuY2UsIG91ciBzYW1wbGUgc2l6ZSBoYXMgaW5jcmVhc2VkLCBzbyB0aGlzIHJlZmxlY3RzIGdyZWF0ZXIgY29uZmlkZW5jZSB0aGF0IHRoZSBvYnNlcnZlZCBudW1iZXIgb2YgaGVhZHMsY29uZGl0aW9uZWQgYnkgdGhlIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBvZiAkXHRoZXRhJCwgd2lsbCBsaWUgd2l0aGluIGEgc21hbGxlciBpbnRlcnZhbC4KCldoaWNoIGxlYWRzIG9uIHRvICoqQmF5ZXNpYW4gQ3JlZGlibGUgaW50ZXJ2YWxzKiogLSB0aGUgQmF5ZXNpYW4gZXF1aXZhbGVudCB0byBmcmVxdWVudGlzdCdzIGNvbmZpZGVuY2UgaW50ZXJ2YWxzLiBCZWNhdXNlIEJheWVzaWFuIGVzdGltYXRlcyBkaXN0cmlidXRpb25zIHJhdGhlciB0aGFuIGZpeGVkIHZhbHVlcywgY3JlZGlibGUgaW50ZXJ2YWxzIGFyZSBhcmd1YWJseSBtb3JlIGludHVpdGl2ZSB0aGFuIGNvbmZpZGVuY2UgaW50ZXJ2YWxzOiB0aGV5IHJlZmxlY3QgdGhlIGEgKDk1JSkgcHJvYmFiaWxpdHkgdGhhdCBvZiBoZXJlIHRoZSB2YWx1ZSBnZW5lcmF0ZWQgYnkgdGhlIHJhbmRvbSB2YXJpYWJsZSB0aGV0YSB3aWxsIGZhbGwgd2l0aGluIHRoZSByYW5nZSAocmF0aGVyIHRoYW4gdGhlIGZyZXF1ZW50aXN0IGludGVycHJldGF0aW9uIHRoYXQgdGhlIHRydWUgdmFsdWUgd2lsbCBmYWxsIHdpdGhpbiB0aGUgY29uZmlkZW5jZSBpbnRlcnZhbCA5NSUgb2YgdGhlIHRpbWUpLgoKTGlrZSBhIGNvbmZpZGVuY2UgaW50ZXJ2YWwsIGEgY3JlZGlibGUgaW50ZXJ2YWwgaXMgc3ltbWV0cmljIGFyb3VuZCB0aGUgbWVhbiwgYW5kIHNwYW5zIHRoZSB4LWF4aXMgZW5vdWdoIHRvIGNvdmVyIDk1JSBvZiB0aGUgYXJlYSB1bmRlciB0aGUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIGN1cnZlLiBBbmQgdGhhdCBpcyBnb29kIGlmIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGlzIGFsc28gc3ltbWV0cmljIC0gYnV0IGFzIGNhbiBiZSBzZWVuIGluIG91ciBleGFtcGxlIGFib3ZlLCB0aGF0IGlzIG5vdCBuZWNlc3NhcmlseSB0aGUgY2FzZSwgd2hlcmUgdGhlIHBvc3RlcmlvciBpcyBza2V3ZWQuCgpJZiB0aGUgZGlzdHJpYnV0aW9uIGlzIHNrZXdlZCB0aGVuLCBpdCBjb3VsZCBiZSBiZXR0ZXIgdG8gY29tcHV0ZSB0aGUgcmVnaW9uIG9mICoqaGlnaGVzdCBwb3N0ZXJpb3IgZGVuc2l0eSAoSFBEKSoqIC0gd2hpY2ggYnkgZGVmaW5pdGlvbiB3aWxsIGJlIHRoZSBuYXJyb3dlc3QgaW50ZXJ2YWwgYWNyb3NzIHRoZSBwb3RlbnRpYWwgdmFsdWVzIGZvciB0aGV0YSwgYnV0IGNvdmVyIDk1JSBvZiB0aGUgYXJlYSB1bmRlciB0aGUgcHJvYmFiaWxpdHkgY3VydmUuIEluIG90aGVyIHdvcmRzLCB3ZSBzdGlsbCBtYWludGFpbiB0aGUgc2FtZSA5NSUgcHJvYmFiaWxpdHkgb2YgdGhldGEgbHlpbmcgd2l0aGluIHRoZSByZWdpb24sIGJ1dCB0aGUgcmVnaW9uIGlzIHRoZSBuYXJyb3dlc3QgaXQgcG9zc2libHkgY2FuIGJlLgoKU28gdG8gZG8gdGhpcywgd2Ugd2FudCB0byBmaW5kIHRoZSBpbnRlcnZhbCBiZXR3ZWVuICRcdGhldGFfe2xvd30kIGFuZCAkXHRoZXRhX3toaWdofSQgc3VjaCBhdDoKCiQkClxpbnRfe1x0aGV0YV97bG93fX1ee1x0aGV0YV97aGlnaH19IHAoXHRoZXRhfHgpIGRcdGhldGE9IDEtXGFscGhhCiQkCgpCdXQgZmluZGluZyB0aGlzIGNhbiBiZSB0cmlja3ksIHBhcnRpY3VsYXJseSB3aXRoIGNvbXB1dGluZyBjbG9zZWQgaW50ZXJ2YWxzLiBUaGUgY29kZSBiZWxvdyBzaG93cyBhIGJydXRlIGZvcmNlIHNvbHV0aW9uLiBUaGUgd2F5IHRvIHRoaW5rIGFib3V0IHRoaXMgaXMgYXMgZm9sbG93czoKKiBDcmVkaWJsZSBpbnRlcnZhbHM6IEdpdmVuIHRoZSBtZWFuIG9mIHRoZSBkaXN0cmlidXRpb24sIGV4cGFuZCB0aGUgcmFuZ2Ugb3V0d2FyZHMgZXF1YWxseSB1bnRpbCA5NSUgb2YgdGhlIGFyZWEgdW5kZXIgdGhlIGN1cnZlIGlzIGNhcHR1cmVkLgoqIEhpZ2hlc3QgcG9zdGVyaW9yIGRlbnNpdHk6IEltYWdpbmUgYSBob3Jpem9udGFsIGxpbmUgbW92aW5nIHNsb3dseSB0b3dhcmRzIHRoZSB4IGF4aXMsIGludGVyY2VwdGluZyB0aGUgZGlzdHJpYnV0aW9uIHR3aWNlLiBPbmNlIHRoZSAKCihOT1RFIFRIRSBHUkFQSCBCRUxPVyBJUyBXUk9ORywgTkVFRFMgRklYSU5HKQoKYGBge3IsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD03LCBmaWcuZnVsbHdpZHRoID0gVFJVRX0KZmluZF9iaW5vbWlhbF9jcmVkaWJsZV9pbnRlcnZhbCA8LSBmdW5jdGlvbihrLCBuLCBwLCBsZWFybmluZ19yYXRlID0gMC41LCBpbml0aWFsX3dpZHRoID0gMC4xLCBjcml0ZXJpb24gPSAwLjEsIG1heF9pdGVyYXRpb25zID0gMTAwMCwgcHJlY2lzaW9uID0gNCkgewogIGJpdCA8LSBpbml0aWFsX3dpZHRoLzIgIyBhbW91bnQgdG8gcHVzaCBhd2F5IGZyb20gbWVhbgogIGZvcihpIGluIDE6bWF4X2l0ZXJhdGlvbnMpIHsKICAgIGFtb3VudCA8LSBwYmV0YShwK2JpdCwgaysxLCBuLWsrMSkgLSBwYmV0YShwLWJpdCwgaysxLCBuLWsrMSkgIyBzdW0gdGhlIGF1YyBiZXR3ZWVuIHAtYml0IGFuZCBwK2JpdAogICAgYml0IDwtIGJpdCAtIGxlYXJuaW5nX3JhdGUqKGFtb3VudCAtICgxLWNyaXRlcmlvbikpICMgZGVjcmVhc2UgaWYgYXVjID4gMC45NSBvciBpbmNyZWFzZSBpZiBhdWMgPCAwLjg1IAogICAgaWYoYWJzKGFtb3VudCAtICgxLWNyaXRlcmlvbikpIDwgMS8oMTBecHJlY2lzaW9uKSkgewogICAgICBicmVhaygpCiAgICB9CiAgfQogIHJldHVybihjKHAtYml0LHArYml0KSkKfQoKZmluZF9iaW5vbWlhbF9oaWdoZXN0X3N0YXJ0X3BvaW50IDwtIGZ1bmN0aW9uKHByZWNpc2lvbiA9IDQsayxuKSB7CiAgeCA8LSBzZXEoMCwxLDEwXi1wcmVjaXNpb24pCiAgcGRmIDwtIGRiZXRhKHgsayxuLWspCiAgcmV0dXJuKHhbbWF4KHBkZikgPT0gcGRmXSkKfQoKZmluZF9iaW5vbWlhbF9ocGQgPC0gZnVuY3Rpb24oayxuLGNyaXRlcmlvbj0wLjEsIGluaXRpYWxfbW92ZW1lbnRfc2l6ZSA9IDAuMSwgbWF4X2l0ZXJhdGlvbnM9MTBeMyxsZWFybmluZ19yYXRlID0gIDAuMDA1LCBwcmVjaXNpb24gPSA0KSB7CiAgcCA8LSBmaW5kX2Jpbm9taWFsX2hpZ2hlc3Rfc3RhcnRfcG9pbnQocHJlY2lzaW9uLGssbikKICBsZWZ0X2xvYyA8LSBwCiAgcmlnaHRfbG9jIDwtIHAKICBiaXQgPC0gaW5pdGlhbF9tb3ZlbWVudF9zaXplCiAgaWYocmVzaWR1YWwgPiAwKSB7ICMgbmVlZCB0byBpbmNyZWFzZSB3aWR0aAogICAgaWYocGJldGEobGVmdF9sb2MgKyBiaXQsIGsrMSwgbi1rKzEpID4gcGJldGEocmlnaHRfbG9jICsgYml0LCBrKzEsIG4taysxKSkgeyAjIGxlZnQgc2lkZSBwZGYgaXMgaGlnaGVyCiAgICAgIGxlZnRfbG9jIDwtIGxlZnRfbG9jLWJpdCAjIG1vdmUgbGVmdAogICAgfSBlbHNlIHsgIyByaWdodCBzaWRlIHBkZiBpcyBoaWdoZXIKICAgICAgcmlnaHRfbG9jIDwtIHJpZ2h0X2xvYytiaXQgIyBtb3ZlIHJpZ2h0CiAgICB9CiAgfSBlbHNlIHsKICAgIGlmKHBiZXRhKGxlZnRfbG9jICsgYml0LCBrKzEsIG4taysxKSA+IHBiZXRhKHJpZ2h0X2xvYyArIGJpdCwgaysxLCBuLWsrMSkpIHsgIyBsZWZ0IHNpZGUgcGRmIGlzIGhpZ2hlcgogICAgICByaWdodF9sb2MgPC0gcmlnaHRfbG9jK2JpdCAjIG1vdmUgcmlnaHQKICAgIH0gZWxzZSB7ICMgcmlnaHQgc2lkZSBwZGYgaXMgaGlnaGVyCiAgICAgIGxlZnRfbG9jIDwtIGxlZnRfbG9jLWJpdCAjIG1vdmUgbGVmdAogICAgfQogIH0KICByZXNpZHVhbCA8LSAoMS1jcml0ZXJpb24pIC0gKHBiZXRhKHJpZ2h0X2xvYywgaysxLCBuLWsrMSktcGJldGEobGVmdF9sb2MsIGsrMSwgbi1rKzEpKSAjIGRpZmZlcmVuY2UgdG8gZS5nLiAwLjk1CiAgICBpZihhYnMocmVzaWR1YWwpIDwgMTBeLXByZWNpc2lvbikgewogICAgICBicmVhaygpCiAgICB9IGVsc2UgewogICAgICBiaXQgPC0gYml0IC0gbGVhcm5pbmdfcmF0ZSpyZXNpZHVhbAogICAgfQogIHJldHVybihjKGxlZnRfbG9jLCByaWdodF9sb2MpKQp9CgpjcmVkaWJsZV9pbnRlcnZhbHMgPC0gZmluZF9iaW5vbWlhbF9jcmVkaWJsZV9pbnRlcnZhbChrLCBuLCBwLCBtYXhfaXRlcmF0aW9ucyA9IDEwXjMsIGNyaXRlcmlvbiA9IDAuMSkKaGlnaGVzdF9wb3N0ZXJpb3JfZGVuc2l0eSA8LSBmaW5kX2Jpbm9taWFsX2hwZChrLG4sIG1heF9pdGVyYXRpb25zID0gMTBeMywgY3JpdGVyaW9uID0gMC4xKQoKcGxvdF9seSh0eXBlID0gJ3NjYXR0ZXInLCBtb2RlID0gJ2xpbmVzJykgJT4lCiAgYWRkX3RyYWNlKHggPSB4LCB5ID0gbGlrZWxpaG9vZF9mLCBuYW1lID0gJ0Jpbm9tKDEwLDAuMiknKSAlPiUKICBhZGRfdHJhY2UoeCA9IHJlcChwLDIpLCB5ID0gYygwLG1heChsaWtlbGlob29kX2YpKSwgbmFtZSA9ICdNZWFuJykgJT4lCiAgIyBhZGRfdHJhY2UoeCA9IHJlcChjcmVkaWJsZV9pbnRlcnZhbHNbMV0sMiksIHkgPSBjKDAsbWF4KGxpa2VsaWhvb2RfZikpLCBuYW1lID0gJ0xvd2VyIGNyZWRpYmxlIGludGVydmFsIGJvdW5kJykgJT4lCiAgIyBhZGRfdHJhY2UoeCA9IHJlcChjcmVkaWJsZV9pbnRlcnZhbHNbMl0sMiksIHkgPSBjKDAsbWF4KGxpa2VsaWhvb2RfZikpLCBuYW1lID0gJ1VwcGVyIGNyZWRpYmxlIGludGVydmFsIGJvdW5kJykgJT4lCiAgYWRkX3RyYWNlKHggPSBwbWluKHBtYXgoeCwgY3JlZGlibGVfaW50ZXJ2YWxzWzFdKSxjcmVkaWJsZV9pbnRlcnZhbHNbMl0pLCB5ID0gbGlrZWxpaG9vZF9mLCBuYW1lID0gJ0NyZWRpYmxlIEludGVydmFsJywgZmlsbCA9ICd0b3plcm95JywgbGluZSA9IGxpc3QoZGFzaCA9ICdkb3QnKSkgJT4lCiAgbGF5b3V0KHRpdGxlID0gJ0NyZWRpYmxlIEludGVydmFsIChlcXVpZGlzdGFudCBhcm91bmQgbWVhbiknKQoKcGxvdF9seSh0eXBlID0gJ3NjYXR0ZXInLCBtb2RlID0gJ2xpbmVzJykgJT4lCiAgYWRkX3RyYWNlKHggPSB4LCB5ID0gbGlrZWxpaG9vZF9mLCBuYW1lID0gJ0Jpbm9tKDEwLDAuMiknKSAlPiUKICBhZGRfdHJhY2UoeCA9IHJlcChwLDIpLCB5ID0gYygwLG1heChsaWtlbGlob29kX2YpKSwgbmFtZSA9ICdNZWFuJykgJT4lCiAgIyBhZGRfdHJhY2UoeCA9IHJlcChjcmVkaWJsZV9pbnRlcnZhbHNbMV0sMiksIHkgPSBjKDAsbWF4KGxpa2VsaWhvb2RfZikpLCBuYW1lID0gJ0xvd2VyIGNyZWRpYmxlIGludGVydmFsIGJvdW5kJykgJT4lCiAgIyBhZGRfdHJhY2UoeCA9IHJlcChjcmVkaWJsZV9pbnRlcnZhbHNbMl0sMiksIHkgPSBjKDAsbWF4KGxpa2VsaWhvb2RfZikpLCBuYW1lID0gJ1VwcGVyIGNyZWRpYmxlIGludGVydmFsIGJvdW5kJykgJT4lCiAgYWRkX3RyYWNlKHggPSBwbWluKHBtYXgoeCwgaGlnaGVzdF9wb3N0ZXJpb3JfZGVuc2l0eVsxXSksaGlnaGVzdF9wb3N0ZXJpb3JfZGVuc2l0eVsyXSksIHkgPSBsaWtlbGlob29kX2YsIG5hbWUgPSAnSGlnaGVzdCBQb3N0ZXJpb3IgRGVuc2l0eScsIGZpbGwgPSAndG96ZXJveScsIGxpbmUgPSBsaXN0KGRhc2ggPSAnZG90JykpICU+JQogIGxheW91dCh0aXRsZSA9ICdIaWdoZXN0IFBvc3RlcmlvciBEZW5zaXR5IChzbWFsbGVzdCBzcHJlYWQgdGhhdCBjb250YWlucyA5NSUgb2YgZGF0YSknKQogIApgYGAKClNvbWUgQmF5ZXNpYW5zIGFyZ3VlIHRob3VnaCB0aGF0IGNyZWRpYmxlIGludGVydmFscyBhbmQgSFBEcyBhcmUgb25seSByZWFsbHkgc29tZXRoaW5nIHRoYXQgYXJlIHVzZWZ1bCB0byBjb21wYXJlIHRvIGZyZXF1ZW50aXN0IGludGVycHJldGF0aW9ucywgYXMgdGhlIGRpc3RyaWJ1dGlvbiBpcyBhbHJlYWR5IGdpdmVuIGJ5IHRoZSBwb3N0ZXJpb3IuCgojIyBDb25qdWdhbmN5IChiZXRhLWJpbm9taWFsKQoKTm93IHRvIGdldCBnZWVreSAtIHlvdSBtaWdodCBoYXZlIGFscmVhZHkgbm90aWNlZCBob3cgZWVyaWx5IHNpbWlsYXIgdGhlIGJldGEgZGlzdHJpYnV0aW9uIGlzIHRvIHRoZSBiaW5vbWlhbCBkaXN0cmlidXRpb24gZnJvbSB0aGUgZm9ybXVsYSAtIGFuZCBpbiBmYWN0IHlvdSBjYW4gdXNlIHRoZSBiZXRhIGRpc3RyaWJ1dGlvbiBhcyBhIGNvbnRpbm91cyBmdW5jdGlvbiBlcXVpdmFsZW50IHRvIHRoZSBiaW5vbWlhbCBmdW5jdGlvbi4gCgokJApwKFx0ZXh0e0g9fWt8IFx0aGV0YSkgXHNpbSBcdGhldGFea1x0aW1lcygxLVx0aGV0YSlee24ta30gXHNpbSBcdGV4dHtCZXRhfVtrKzEsbi1rKzFdCiQkCgpCb3RoIGJpbm9taWFsIGFuZCBiZXRhIGxpa2VsaWhvb2RzIGFyZSBzY2FsZWQgdGhvdWdoIChub3JtYWxpemVkKSwgc28gdGhhdCB0aGUgc3VtIG9mIHRoZWlyIHByb2JhYmlsaXRlcyB0b3RhbCAxLgpGb3IgdGhlIGJldGEgZGlzdHJpYnV0aW9uLCB0aGUgc2NhbGluZyBpcyBhY2hpZXZlZCBsaWtlIHRoaXM6CgokJApCZXRhW1xhbHBoYSxcYmV0YV0gPSBcdGhldGFee1xhbHBoYS0xfVx0aW1lcygxLVx0aGV0YSlee1xiZXRhLTF9IFx0aW1lcyBcZnJhY3sxfXtcdGV4dHtCfShcYWxwaGEsXGJldGEpfQokJApXaGVyZQoKJCQKXGZyYWN7MX17XHRleHR7Qn0oXGFscGhhLFxiZXRhKX0gPSBcZnJhY3tcR2FtbWEoXGFscGhhK1xiZXRhKX17XEdhbW1hKFxhbHBoYSkgXHRpbWVzIFxHYW1tYShcYmV0YSl9ID0gXGZyYWN7KFxhbHBoYStcYmV0YS0xKSF9eyhcYWxwaGEtMSkhIFx0aW1lcyAoXGJldGEtMSkhfQokJAoKU28gaWYgc3VjY2Vzc2VzICRcYWxwaGEgPSBrKzEkIGFuZCBmYWlsdXJlcyAkXGJldGEgPSBuIC0gayArIDEkLCB0aGVuOgoKJCQKXGZyYWN7KFxhbHBoYStcYmV0YS0xKSF9eyhcYWxwaGEtMSkhIFx0aW1lcyAoXGJldGEtMSkhfT1cZnJhY3soKGsrMSkrKG4taysxKS0xKSF9eygoaysxKS0xKSEgXHRpbWVzICgobi1rKzEpLTEpIX09XGZyYWN7KG4rMSkhfXsoaykhXHRpbWVzKG4taykhfSA9CntuKzEgXGNob29zZSBrIH0gPSAobisxKSBcdGltZXMge24gXGNob29zZSBrIH0KJCQKCk5vdyB3ZSBkZWZpbmUgdGhlIGJpbm9taWFsIGRpc3RyaWJ1dGlvbiBmb3IgY29tcGFyaXNvbjoKCiQkClx0ZXh0e0Jpbm9tfShuLHApID0ge24gXGNob29zZSBrIH0gW1x0aGV0YV57a31cdGltZXMoMS1cdGhldGEpXntuLWt9XSAgCiQkCgoKQW5kIHRodXM6CgokJApCZXRhW2srMSxuLWsrMV0gPSAobisxKSBcdGltZXMgXHRleHR7Qmlub219KG4scCkKJCQKClRoaXMgcmVsYXRpb25zaGlwIGhlbHBzIHVzIGNvbWJpbmUgYmlub21pYWwgbGlrZWxpaG9vZHMgYW5kIGJldGEgcHJpb3JzIHRvIGNyZWF0ZSBhIHBvc3RlcmlvciBpbiB3aGF0IGlzIGNhbGxlZCAqKmNvbmp1Z2FuY3kqKi4gQ29uanVnYW5jeSBvY2N1cnMgd2hlbiB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBpcyBpbiB0aGUgc2FtZSBmYW1pbHkgb2YgcHJvYmFiaWxpdHkgZGVuc2l0eSBmdW5jdGlvbnMgYXMgdGhlIHByaW9yIGJlbGllZiwgYnV0IHdpdGggbmV3IHBhcmFtZXRlciB2YWx1ZXMgKHVwZGF0ZWQgdG8gcmVmbGVjdCB3aGF0IGhhcyBiZWVuIGxlYXJuZWQgZnJvbSB0aGUgZGF0YSkuIFRoZSBwb3N0ZXJpb3IgY29tZXMgZnJvbSB0aGUgc2FtZSBmYW1pbHkgYXMgdGhlIHByaW9yLCByYXRoZXIgdGhhbiB0aGUgZGF0YSdzIGRpc3RyaWJ1dGlvbi4KCgpBbGwgdGhlIHRocmVlIGNvaW4gZXhhbXBsZXMgYWJvdmUgd2VyZSAqKmV4YW1wbGVzIG9mIGNvbmp1Z2FuY3kqKi4gRm9yIGV4YW1wbGUsIHRoZSBzZWNvbmQgaGFkIGEgcHJpb3IgdGhhdCB3YXMgdW5pZm9ybSwgZXhwcmVzc2VkIGFzIGEgYmV0YSBkaXN0cmlidXRpb24sIHdoZXJlYXMgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gd2FzIGEgYmlub21pYWwgZGlzdHJpYnV0aW9uLiBUaGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiB3YXMgdGh1cyBiZXRhLCBzaW5jZSBpdCBpcyB0aGUgc2FtZSBmYW1pbHkgb2YgcHJvYmFiaWxpdHkgZGVuc2l0eSBmdW5jdGlvbnMgYXMgdGhlIHByaW9yIGJlbGllZiAoYmV0YSksIGJ1dCB3aXRoIG5ldyBwYXJhbWV0ZXIgdmFsdWVzIGxlYXJudCBmcm9tIHRoZSBwcm9iYWJpbGl0eSBtYXNzIGZ1bmN0aW9uIGRlcml2ZWQgZnJvbSB0aGUgbmV3IGRhdGEuIE5vdGUgdGhhdCB0aGUgcG9zdGVyaW9yIGRpZCBub3QgZm9sbG93IGEgYmlub21pYWwgZGlzdHJpYnV0aW9uLCBidXQgZm9sbG93ZWQgYSBiZXRhIG9uZSwgc2luY2UgdGhpcyBpcyB3aGF0IHRoZSBwcmlvciB1c2VkLiBDb25qdWdhdGVzIGFyZSB0aHVzIHZlcnkgdXNlZnVsIGluIGhlbHBpbmcgZGVyaXZlIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uLgoKV2l0aG91dCBjb25qdWdhbmN5LCBvbmUgaGFzIHRvIGRvIHRoZSBpbnRlZ3JhbCwgd2hpY2ggaXMgb2Z0ZW4gaW1wb3NzaWJsZSB0byBhY3R1YWxseSBldmFsdWF0ZSwgYW5kIGlzIG9uZSBvZiB0aGUgcmVhc29ucyBiYXllc2lhbiB3YXMgbm90IHBvcHVsYXIgaW4gdGhlIDIwdGggY2VudHVyeSAoYmVmb3JlIGNvbXB1dGluZyBhbGxvd2VkIHJlc2VhcmNoZXJzIHRvIGNvbXB1dGUgaW50ZWdyYWxzIG51bWVyaWNhbGx5KS4gTm93YWRheXMsIHNhbXBsaW5nIG1ldGhvZHMgc3VjaCBhcyBNYXJrb3YtY2hhaW4gbW9udGUtY2FybG8gKE1DTUMpIGFyZSBvZnRlbiB1c2VkIHRvIHNpbXVsYXRlIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uLgoKIyMgQ29uanVnYW5jeSAoZ2FtbWEtcG9pc3NvbikKCkFzIHdlbGwgYXMgdGhlIGJldGEtYmlub21pYWwgY29uanVnYXRlIGZhbWlseSwgd2UgYWxzbyBoYXZlIHRoZSBnYW1tYS1wb2lzc29uIGNvbmp1Z2F0ZSBmYW1pbHkuIAoKVGhlIHBvaXNzb24gZnVuY3Rpb24gaXMgc3BlY2lmaWVkIGFzOgoKJCQKUChYPWspPVxmcmFje1xsYW1iZGFee2t9fXtrIX1lXnstXGxhbWJkYX0gXHRleHR7IGZvciB9IGs9MCwxLC4uLiwKJCQKCldoZXJlYXMgdGhlIGdhbW1hIGZhbWlseSBpcyByZWxhdGVkIHRvIHRoZSBnYW1tYSBmdW5jdGlvbiAod2l0ayAkayxcdGhldGEkIGFuZCAkXGFscGhhLFxiZXRhJCBwYXJhbWV0ZXJpemF0aW9ucyBsaXN0ZWQgYmVsb3cpOgoKJCQKZih4KT1cZnJhY3sxfXtcR2FtbWEoaylcdGhldGFea314XntrLTF9ZV57LXgvXHRoZXRhfT1cZnJhY3tcYmV0YV57XGFscGhhfX17XEdhbW1hKGspfXhee1xhbHBoYS0xfWVeey1cYmV0YSB4fQokJApBbmQgaGVuY2Ugd2UgY2FuIHNlZSB0aGF0IHRoYXQgd2hlcmUgJG4kIGlzIGEgcG9zaXRpdmUgaW50ZWdlciwgYW5kICRcdGhldGE9MSQsIHdlIG9ic2VydmUgdGhlIHNwZWNpYWwgY2FzZSB0aGF0ICRcR2FtbWEoayk9KGstMSkhJCBzbyB0aGF0IAoKTkVFRCBUTyBXT1JLIE9OIFRISVMgQklUCgokJApcZnJhY3sxfXtcR2FtbWEoaylcdGltZXNcdGhldGFea314XntrLTF9ZV57LXgvXHRoZXRhfT0KXGZyYWN7MX17KGstMSkhXHRpbWVzMV5rfXhee2stMX1lXnsteC9cdGhldGF9PQpcZnJhY3tcbGFtYmRhXntrfX17ayF9ZV57LVxsYW1iZGF9CiQkCgojIyBUaGlua2luZyBhYm91dCBCYXllc2lhbiBpbiB0ZXJtcyBvZiBwcmVkaWN0aW5nIHRoaW5ncwoKVGhlcmUgYXJlIHR3byBzb3VyY2VzIG9mIHVuY2VydGFpbnR5IHdoZW4gYnVpbGRpbmcgc3RhdGlzdGljYWwgbW9kZWxzIHRvIHByZWRpY3QgdGhpbmdzOgoKKiBVbmNlcnRhaW50eSBkdWUgdG8gdGhlIGZhY3QgYW55IGZ1dHVyZSB2YWx1ZSBpcyBpdHNlbGYgYSByYW5kb20gZXZlbnQsICRQKHl8XHRoZXRhKSQgKGJlY2F1c2UgZnV0dXJlIGV2ZW50cyBhcmUgZXNzZW50aWFsbHkgc2FtcGxlcyB0aGF0IGhhdmUgZXJyb3IgY29uZGl0aW9uZWQgYnkgJFx0aGV0YSQpCiogVW5jZXJ0YWludHkgaW4gdGhlIHBhcmFtZXRlciB2YWx1ZXMgd2hpY2ggaGF2ZSBiZWVuIGVzdGltYXRlZCBvbiB0aGUgYmFzaXMgb2YgcGFzdCBkYXRhLCAkUChcdGhldGF8WCkkIChmb3IgZXhhbXBsZSwgYSBjb2VmZmljaWVudCBlc3RpbWF0ZWQgaW4gYSByZWdyZXNzaW9uIG1vZGVsKQoKQ2xhc3NpY2FsIG1vZGVscyBkZWFsIHdpdGggcG9pbnQgMSwgbWFraW5nIGEgcG9pbnQgZXN0aW1hdGUgaW4gdGhlIGZ1dHVyZSBiYXNlZCBvbiB0aGUgJ2Jlc3QnIHBhcmFtZXRlcnMgZXN0aW1hdGVkIGZyb20gcGFzdCBkYXRhLiBUaGlzIGlzIGVxdWl2YWxlbnQgdG8gZm9ybWluZyBhIGxpa2VsaWhvb2QgKGkuZS4gaW5jb3Jwb3JhdGluZyBuZXcgZGF0YSkuCldoYXQgdGhleSBkb24ndCBkbyB0aG91Z2ggaXMgdGhpbmsgYWJvdXQgcG9pbnQgMiwgdGhhdCB0aGUgc2VlbWluZ2x5IG9wdGltdW0gbW9kZWwgZXN0aW1hdGVkIGl0c2VsZiBtaWdodCBiZSBpbmNvcnJlY3Qgc2luY2UgdGhlIHRydWUgdmFsdWVzIG9mICRcdGhldGEkIGFyZSBub3QgZml4ZWQsIGFuZCB0aGlzIGlzIGVxdWl2YWxlbnQgdG8gbm90IGJ1aWxkaW5nIGluIGFueSBwcmlvciBiZWxpZWZzLiBJbiBhIHdheSwgYnkgZ2l2aW5nIGEgcG9pbnQgZXN0aW1hdGUsIHRoZSBtb2RlbHMgZ2VuZXJhdGUgYSBmYWxzZSBzZW5zZSBvZiBwcmVjaXNpb24sIGFuZCB0aGUgY29uZmlkZW5jZSBpbnRlcnZhbHMgYXJvdW5kcyBhbnkgZXN0aW1hdGUgaXMgb25seSBwcmVkaWNhdGVkIG9uIHRoZSBpZGVhIHRoZXJlIGlzIHNhbXBsaW5nIHJhbmRvbW5lc3MsIHJhdGhlciB0aGFuIHJhbmRvbW5lc3MgYXNzb2NpYXRlZCB3aXRoICRcdGhldGEkIGl0c2VsZi4KCkluIG90aGVyIHdvcmRzLCBjbGFzc2ljYWwgbW9kZWxzIHNlZWsgdG8gYmVzdCBmaXQgdGhlIG5ldyBldmlkZW5jZSAodHJhZGl0aW9uYWxseSB0aHJvdWdoIG1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0aW9uIGZvciBnZW5lcmFsaXplZCBsaW5lYXIgbW9kZWxzKSwgd2hlcmVhcyBiYXllc2lhbiBtb2RlbHMgaW5jb3Jwb3JhdGUgcHJpb3IgYmVsaWVmcyBhcyB3ZWxsLgoKSW1hZ2luZSB0aGVuLCBpZiB3ZSB3YW50IHRvIGVzdGltYXRlIHRoZSBpbXBhY3Qgb2YgeCBvbiB5IHRvIG1ha2UgYSBmdXR1cmUgcHJlZGljdGlvbiwgd2UgY2FuIGRvIHRoZSBmb2xsb3dpbmc6CgokJApmKHl8eCk9IFxpbnQgZih5fFx0aGV0YSx4KWYoXHRoZXRhfHgpIFxwYXJ0aWFsKFx0aGV0YSkKJCQKCldoZXJlICRmKHl8XHRoZXRhLHgpJCByZXByZXNlbnRzIHRoZSBtb2RlbGxpbmcgcmFuZG9tIHNhbXBsaW5nIGVycm9yIGFzIGluIGZyZXF1ZW50aXN0IHJlZ3Jlc3Npb24gKHRoZSBsaWtlbGlob29kIGZ1bmN0aW9uKSwgYW5kICRmKFx0aGV0YXx4KSQgcmVwcmVzZW50aW5nIHRoZSBlcnJvciBhcmlzaW5nIGZyb20gJFx0aGV0YSQgYmVpbmcgYSByYW5kb20gdmFyaWFibGUgcmF0aGVyIHRoYW4gYmVpbmcgdHJlYXRlZCBhcyBhIGZpeGVkIHF1YW50aXR5LgoKTm93IHdoeSBpcyBpdCBhbiBpbnRlZ3JhbD8gTGV0J3MgdGhpbmsgb2YgdGhlIGNvaW4gZXhhbXBsZSBhYm92ZSB3aGVyZSB0aGVyZSBhcmUgb25seSB0d28gdHlwZXMgb2YgY29pbnMgaW4gdGhlIGVjb25vbXkuIElmIHdlIHdhbnQgdG8ga25vdyB3aGF0IGlzIHRoZSBwcm9iYWJpbGl0eSB3ZSBnZXQgaGVhZHMsIHJhdGhlciB0aGFuIHRoZSBwcm9iYWJpbGl0eSB0aGF0IHdlIGhhdmUgYSBmYWlyIG9yIGEgYmlhc2VkIGNvaW4uIAoKJCQKUChcdGV4dHtoZWFkc318az0yKQpcXCA9IFAoXHRleHR7aGVhZHN9fFx0ZXh0e2ZhaXJ9LGs9MikgXHRpbWVzIFAoXHRleHR7ZmFpcn18az0yKSArIFAoXHRleHR7aGVhZHN9fFx0ZXh0e2JpYXNlZH0saz0yKSBcdGltZXMgUChcdGV4dHtiaWFzZWR9fGs9MikKJCQKCkFzIGJlZm9yZSwgd2Ugc3VtbWFyaXNlIHRoZSBwcm9iYWJpbGl0eSBtYXNzIGZ1bmN0aW9uIHJlbGF0aW5nIHRvICRcdGhldGEkIGFzIGJlaW5nIDAuNSAoZmFpcikgZm9yIDkwJSBvZiBjb2lucyBpbiB0aGUgZWNvbm9teSwgYW5kICRgciBrL25gIChiaWFzZWQpIGZvciAxMCUgb2YgdGhlc2UgY29pbnMsIHdoaWNoIGdpdmVzIHVzIHRoZSBmb2xsb3dpbmc6CgokJApQKFx0ZXh0e2hlYWRzfGs9YHIga2B9KSBcXCAKPSBcc3VtX3tcdGhldGF9e1AoXHRleHR7aGVhZHN9fFx0aGV0YVx0ZXh0eyxrPWByIGtgfSkgXHRpbWVzIFAoXHRoZXRhfFx0ZXh0e2s9YHIga2B9KSB9CiQkCgpBbmQgYnkgdGFraW5nIGludG8gYWNjb3VudCBhbGwgdGhlIHBvc3NpYmxlIHZhbHVlcyB0aGF0IHRoZXRhIGNhbiB0YWtlLCB3ZSBhcmUgZXNzZW50aWFsbHkgaW50ZWdyYXRpbmcgYWxvbmcgdGhlIAoKJCQKUChcdGV4dHtoZWFkc3xrPWByIGtgfSkgPSBcaW50IFAoXHRleHR7aGVhZHN9fFx0aGV0YSxrPWByIGtgKSBcdGV4dHsgfVAoXHRoZXRhfGs9YHIga2ApIFx0ZXh0eyB9IFxwYXJ0aWFsKFx0aGV0YSkKXFwKXHRleHR7d2hlcmUgfVx0aGV0YSA9ClxiZWdpbntjYXNlc30KYHIgay9uYCAmIDEwXCUgXHRleHR7IG9mIHRoZSB0aW1lfVxcCjAuNSAmIDkwXCUgXHRleHR7IG9mIHRoZSB0aW1lfVxcClxlbmR7Y2FzZXN9CiQkCgoKTkVFRCBUTyBSRS1XUklURSBFVkVSWVRISU5HIEJFTE9XIFRISVMKCiEhISEhISEhISEhISEKISEhISEhISEhISEhIQohISEhISEhISEhISEhCiEhISEhISEhISEhISEKISEhISEhISEhISEhIQohISEhISEhISEhISEhCiEhISEhISEhISEhISEKISEhISEhISEhISEhIQohISEhISEhISEhISEhCgoKTm93IGJlY2F1c2UgdGhpcyBlcXVhdGlvbiBpcyBkb25lIHRocm91Z2ggY29uanVnYW5jeSwgdGhpcyBpcyBlYXN5IHRvIGV2YWx1YXRlLiBBbm90aGVyIHdheSB0aGVuIG9mIGxvb2tpbmcgYXQgaXQgZm9yIHRoaXMgZXhhbXBsZSBpcyBieSByZWFycmFuZ2luZyBiYXllcyB0aGVyb2VtOgoKJCQKUCh5fFgpID0gXGZyYWN7UCh5fFx0aGV0YSxYKSBcdGltZXMgUChcdGhldGF8WCl9e1AoXHRoZXRhfHksWCl9Cj0gXGZyYWN7UChcdGV4dHtoZWFkc318XHRleHR7ZmFpcn0saz0yKSBcdGltZXMgUChcdGhldGF8WCl9e1AoXHRoZXRhfHksWCl9CiQkCgoKJCQKUChcdGhldGF8WCkgPVxmcmFje1AoWHxcdGhldGEpIFx0aW1lcyBQKFx0aGV0YSl9e1AoWCl9ID0gXGZyYWN7UChYfFx0aGV0YSkgXHRpbWVzIFAoXHRoZXRhKX17UChYfFx0aGV0YSkgXHRpbWVzIFAoXHRoZXRhKSArIFAoWHxcdGhldGEnKSBcdGltZXMgUChcdGhldGEnKX0gXFwKCiQkCgoKCkFuZCBoZW5jZSBpdCBjYW4gYmUgc2VlbiB0aGF0IHRvIGdldCB0aGUgZnVsbCBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb24gYXNzb2NpYXRlZCB3aXRoIGdldHRpbmcgaGVhZHMsIHlvdSBuZWVkIHRvIGFzc2VzcyBhbGwgcG9zc2libGUgdmFsdWVzIHRoYXQgdGhldGEgY291bGQgdGFrZS4KCgokJApQKHl8WCkgCj0gXGZyYWN7UCh5fFx0aGV0YSxYKSBcdGltZXMgUChcdGhldGF8WCl9e1AoXHRoZXRhfHksWCl9Cj0gXGZyYWN7UChcdGV4dHtoZWFkc318XHRoZXRhLGs9MikgXHRpbWVzIFAoXHRoZXRhfGs9Mil9e1AoXHRoZXRhfFx0ZXh0e2hlYWRzLGs9Mn0pfQokJAoKCiQkClAoXHRleHR7aGVhZHN8az0yfSkgPQpcZnJhY3tQKFx0ZXh0e2hlYWRzfXxcdGV4dHtmYWlyLGs9Mn0pIFx0aW1lcyBQKFx0ZXh0e2ZhaXJ8az0yfSl9e1AoXHRleHR7ZmFpcn18XHRleHR7aGVhZHN9LGs9Mil9ICsKXGZyYWN7UChcdGV4dHtoZWFkc318XHRleHR7Ymlhc2VkLGs9Mn0pIFx0aW1lcyBQKFx0ZXh0e2JpYXNlZHxrPTJ9KX17UChcdGV4dHtiaWFzZWR9fFx0ZXh0e2hlYWRzfSxrPTIpfSBcXAoKJCQKCkFzIGJlZm9yZSwgd2Ugc3VtbWFyaXNlIHRoZSBwcm9iYWJpbGl0eSBtYXNzIGZ1bmN0aW9uIHJlbGF0aW5nIHRvICRcdGhldGEkIGFzIGJlaW5nIDAuNSAoZmFpcikgZm9yIDkwJSBvZiBjb2lucyBpbiB0aGUgZWNvbm9teSwgYW5kIGByIGtgIChiaWFzZWQpIGZvciAxMCUgb2YgdGhlc2UgY29pbnMsIHdoaWNoIGdpdmVzIHVzIHRoZSBmb2xsb3dpbmc6CgokJApQKFx0ZXh0e2hlYWRzfGs9Mn0pID0gUChcdGV4dHtoZWFkc318XHRoZXRhXHRleHR7LGs9Mn0pIFx0aW1lcyBQKFx0aGV0YXxcdGV4dHtrPTJ9KSAKJCQKCiQkClAoXHRleHR7aGVhZHN9KSA9IFAoXHRleHR7aGVhZHN9fFx0ZXh0e2ZhaXJ9KSBcdGltZXMgUChcdGV4dHtmYWlyfSkgKyBQKFx0ZXh0e2hlYWRzfXxcdGV4dHtiaWFzZWR9KSBcdGltZXMgUChcdGV4dHtiaWFzZWR9KQokJAoKCiQkClAoWCxcdGhldGF8az0yKSA9IFxmcmFje1AoXHRleHR7aGVhZHN9fFx0aGV0YSxrPTIpIFx0aW1lcyBQKFx0aGV0YXxYKX17UChoZWFkc3xrPTIpfQokJAoKJCQKUCh5fFgpID0gXGZyYWN7UCh5fFx0aGV0YSxYKSBcdGltZXMgUChcdGhldGF8WCl9e1AoXHRoZXRhfHksWCl9CiQkCgoKTGV0J3Mgc2F5IHdlIGJlbGlldmUgdGhlIHNhbXBsaW5nIGVycm9yIG9mIHkgdG8gZm9sbG93IGEgbm9ybWFsIGRpc3RyaWJ1dGlvbiwgY29uZGl0aW9uZWQgYnkgJFx0aGV0YSQgKGNhcHR1cmluZyB0aGUgZmlyc3Qgc291cmNlIG9mIHVuY2VydGFpbnR5KSwgd2hpY2ggd2Ugd291bGQgbm9ybWFsbHkgc29sdmUgdGhyb3VnaCBNTEU6CgokJApmKHl8XHRoZXRhKSA9IFxmcmFjezF9e1xzaWdtYVxzcXJ0ezJccGl9fVx0ZXh0e2V4cH0oXGZyYWN7KHktXHRoZXRhKV4yfXsyXHNpZ21hXjJ9KQokJAokJApmKHl8XHRoZXRhLFgpID0gXGZyYWN7MX17XHNpZ21hXHNxcnR7MlxwaX19XHRleHR7ZXhwfShcZnJhY3soeS1YXGJldGEpXjJ9ezJcc2lnbWFeMn0pCiQkCgoKVGhlbiB3ZSBqdXN0IG5lZWQgdG8gZGVyaXZlICRmKFx0aGV0YXx4KSQgaW4gb3JkZXIgdG8gbWFrZSBhIGZ1dHVyZSBwcmVkaWN0aW9uIHRocm91Z2ggYmF5ZXMgKGFuZCB0aGlzIHRlcm0gY2FwdHVyZXMgdGhlIGVycm9yIGFzc29jaWF0ZWQgd2l0aCBvdXIgZXN0aW1hdGlvbiBvZiB0aGV0YSBmcm9tIHRoZSBleG9nZW5vdXMgdmFyaWFibGVzKS4gCgpOb3cgZm9yIGZyZXF1ZW50aXN0cywgdGhlIHBkZiAgJGYoXHRoZXRhfHgpJCBpcyBlcXVhbCB0byAxIGF0IHRoZSB0cnVlIHZhbHVlIG9mIHRoZXRhLCBhbmQgemVybyBlbHNld2hlcmUsIGFzIHRoZXRhIGlzIGZpeGVkIChzbyB0aGVyZSBpcyBvbmx5IG9uZSBwZXJmZWN0IHZhbHVlKS4KClRob3VnaCBmb3IgQmF5ZXNpYW5zLCB0aGUgcGRmIGlzIGNvbmRpdGlvbmVkIGJ5IHByaW9yIGJlbGllZnMgYWJvdXQgJFx0aGV0YSQuIFRoZXNlIGFyZSByZXByZXNlbnRlZCBhcyBhIHBvc3RlcmlvciBhcHByb3hpbWF0ZWQgZnJvbSB0aGUgcHJvZHVjdCBvZiB0aGUgbGlrZWxpaG9vZCBvZiBvYnNlcnZpbmcgdGhlIGV4b2dlbm91cyB2YXJpYWJsZXMgZ2l2ZW4gJFx0aGV0YSQsIGFuZCB0aGUgcHJpb3IgYmVsaWVmcyBhc3NvY2lhdGVkIHdpdGggJFx0aGV0YSQ6CgokJApmKFx0aGV0YXx4KSBcc2ltIGYoXHRoZXRhKSBcdGltZXMgZih4fFx0aGV0YSkKJCQKVG8gY2FwdHVyZSB0aGUgcmFuZG9tbmVzcyBvZiB0aGUgJFx0aGV0YSQsIHdlIG1pZ2h0IGFsc28gYmVsaWV2ZSBvdXIgcHJpb3IgJGYoXHRoZXRhKSQgZm9sbG93cyBhIG5vcm1hbCBkaXN0cmlidXRpb24sIGJ1dCB3aXRoIG1lYW4gJEUoWCk9YiQgYW5kIHZhcmlhbmNlICRWYXIoWCk9ZF4yJC4gQXMgc3VjaCwgdGhlIGRpc3RyaWJ1dGlvbiB0aHVzIGRlc2NyaWJlZCBpcyAkWCBcc2ltIE4oYixkXjIpJAoKVGhlbiB0aGUgcHJpb3IgY2FuIGJlIGRlcml2ZWQgZnJvbSB0aGUgbm9ybWFsIHBkZiAkeCQ6CgokJApmKFx0aGV0YSkgPSBcZnJhY3sxfXtkXHNxcnR7MlxwaX19XHRleHR7ZXhwfShcZnJhY3soXHRoZXRhLWIpXjJ9ezJkXjJ9KQokJAoKTm93IGxldCdzIHRha2UgdGhlIG9ic2VydmVkIGRhdGEgJHg9KHhfMSx4XzMsLi4uLHhfbikkIGFuZCB0cmVhdCBpdCBhcyBhIHJhbmRvbSBzYW1wbGUgb2Ygc2l6ZSAkbiQgb2YgYSAqKnJhbmRvbSoqIHZhcmlhYmxlICRYJCB3aXRoIG1lYW4gJEUoWCk9XHRoZXRhJCBhbmQgdmFyaWFuY2UgJFZhcihYKT1cc2lnbWFeMiQsIGFuZCBmb2xsb3dzIGEgbm9ybWFsIGRpc3RyaWJ1dGlvbiB0aHVzIGRlc2NyaWJlZCBhcyAkWCBcc2ltIE4oXHRoZXRhLFxzaWdtYV4yKSQKClRoZW4gdGhlIGxpa2VsaWhvb2QgZm9yIGV2ZXJ5IG9iZXJ2YXRpb24gJHhfaSQgZnJvbSB0aGUgd2hvbGUgc2FtcGxlICR4JDoKCiQkCmYoeHxcdGhldGEpID0gXHByb2Rfe2k9MX1ee259IGYoeF9pfFx0aGV0YSkgPSBccHJvZF97aT0xfV57bn0gXGZyYWN7MX17XHNpZ21hXHNxcnR7MlxwaX19ZXhwKFxmcmFjeyh4X2ktXHRoZXRhKV4yfXsyXHNpZ21hXjJ9KQokJAoKCmBgYCB7ciwgZWNobyA9IEYsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD03fQoKCgpgYGAKCgo=